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$.