Initially you have the text with lowercase english letters.

You have to proceed \(q_1\) queries: replace all occurrences of letter \(c_i\) in the text with some string \(str_i\).

Now you have to find \(text_i\), where \(text_i\) - is the letter on i-th position in the text after all replacements. Positions in the \(text\) are numbered from 1.

\(INPUT\)

The first line of input contains three integers \(n, q_1, q_2\) \((1 \leq n \leq 200000, 0 \leq q_1, q_2 \leq 200000)\) - a length of the text, a number of replacements, a number of queries where the position was asked.

The second line contains \(text\) - a string of length n which consists of lowercase english letters.

Then follow \(q_1\) lines. The i-th of these lines contains \(c_i\) and \(str_i\). The \(c_i\) is a lowercase english letter. The \(str_i\) is nonempty string which consists of lowercase english letters.

Guaranteed that sum of lengths of all \(str_i\) is not greater than \(200000\).

Then follow \(q_2\) lines. The i-th of these lines contains \(pos_i\) \((1 \leq pos_i \leq 10^{16})\).

\(OUTPUT\)

For each \(pos_i\) print \(text_{pos_i}\) or "none" (without quotes) if the length of the text is less than \(pos_i\).