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++, 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, 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

?