All Tracks Data Structures Advanced Data Structures Problem

Text editor
Tag(s):

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: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

November Clash '16

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications