There is a string $s$, initially $s$ is the single character a.

Perform $n$ operations sequentially. In the $i$-th operation, you are given a character $c_i$ and a string $t_i$, which means replacing all occurrences of the character $c_i$ in $s$ simultaneously with the string $t_i$.

Given $l$ and $r$, find the substring $s_l, \dots, s_r$ after $n$ operations.

Input

The first line contains three integers $l, r, n$.

The next $n$ lines each contain a character $c_i$ and a string $t_i$, separated by a space.

Output

A single line containing $r-l+1$ characters, representing $s_l, \dots, s_r$ in order.

Examples

Input 1

3 8 4
a ab
a bc
c de
b bbb

Output 1

bdebbb

Constraints

For $100\%$ of the data, $1 \le n \le 2 \times 10^5$, $\sum |t_i| \le 2 \times 10^5$, $1 \le l \le r \le \min(|s|, 10^{18})$, $r-l+1 \le 2 \times 10^5$. All characters involved in this problem are lowercase English letters.

• Subtask 1 ($50\%$): $n \le 2000$, $r-l+1 \le 2000$.
• Subtask 2 ($50\%$): No additional constraints.