Find and Replace

Time limit2sMemory limit1024 MB

Summary

Starting from "a", apply letter-to-string replacements, then print the substring from position l to position r of the final string.

Level: Medium6 of 10
Topics: Recursion, Dynamic programming, String
Solved: No attempts yet

Problem

Bessie is using miV, the newest text-editing software. Its find-and-replace feature lets her find every occurrence of a lowercase English letter $c$ and replace each one with a nonempty string $s$ of lowercase letters. For example, given the string "ball", if Bessie picks $c$ to be 'l' and $s$ to be "na", the string becomes "banana".

Bessie starts with the string "a" and applies a number of these operations, which produces a final string $S$ . Since $S$ can be very long, for given $l$ and $r$ with $1\le l\le r\le \min(|S|,10^{18})$ , she wants to know the substring $S_{l\dots r}$ from the $l$ -th to the $r$ -th character, inclusive.

The sum of $|s|$ over all operations is at most $2\cdot 10^5$ , and $r-l+1\le 2\cdot 10^5$ .

Input

The first line contains $l$ , $r$ , and the number of operations. Each of the following lines describes one operation and contains $c$ and $s$ . All characters are lowercase English letters from 'a' to 'z'.

Output

Print the string $S_{l\dots r}$ on a single line.

Hint

The string changes as follows:

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

Examples1

Example 1
Input
```
3 8 4
a ab
a bc
c de
b bbb
```
Expected output
```
bdebbb
```