Text editor
Tag(s):

## AVL tree, Data Structures, Hard

Problem
Editorial
Analytics

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

SAMPLE INPUT
3 2 5
aab
a ab
b aba
1
3
7
11
12

SAMPLE OUTPUT
a
b
b
a
none

Explanation

Text after first replacement is "ababb".

Text after second replacement is "aabaaabaaba".

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 512 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in Challenge Name

November Clash '16

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Graphs
• Data Structures > Advanced Data Structures
• Algorithms > Searching