Find and Replace

문제

Bessie is using the latest and greatest innovation in text-editing software, miV! Its powerful find-and-replace feature allows her to find all occurrences of a lowercase English letter $cc$ and replace each with a nonempty string of lowercase letters $ss$. For example, given the string "ball", if Bessie selects $cc$ to be 'l' and $ss$ to be "na", the given string transforms into "banana".

Bessie starts with the string "a" and transforms it using a number of these find-and-replace operations, resulting in a final string $SS$. Since $SS$ could be massive, she wants to know, given $ll$ and $rr$ with $1\le l\le r\le \min (\mathrm{\mid }S\mathrm{\mid },{10}^{18})1\backslash le\; l\backslash le\; r\backslash le\; \backslash min(|S|,10^\{18\})$, what $S_{l\dots r}S\_\{l\backslash dots\; r\}$ (the substring of $SS$ from the $ll$-th to the $rr$-th character inclusive) is.

It is guaranteed that the sum of $\mathrm{\mid }s\mathrm{\mid }|s|$ over all operations is at most $2\cdot {10}^{5}2\backslash cdot\; 10^5$, and that $r-l+1\le 2\cdot {10}^{5}r-l+1\backslash le\; 2\backslash cdot\; 10^5$.

입력

The first line contains $ll$, $rr$, and the number of operations.

Each subsequent line describes one operation and contains $cc$ and $ss$ for that operation. All characters are in the range 'a' through 'z'.

출력

Output the string $S_{l\dots r}S\_\{l\backslash dots\; r\}$ on a single line.

힌트

The string is transformed as follows:

a $\to \backslash rightarrow$ ab $\to \backslash rightarrow$ bcb $\to \backslash rightarrow$ bdeb $\to \backslash rightarrow$ bbbdebbb

3 8 4
a ab
a bc
c de
b bbb

bdebbb