盛盛要和朋友们做个字符游戏，他有一个字符串S，最开始里面只有一个字符a，之后要对这个字符串进行若干次操作，每次将其中每一个字符c替换成某个字符串s（例如对于字符串ball，将其中的l替换为na后将会变为banana）。现在给定l,r，需要输出S[l..r]（也就是S的第l个字符到第r个字符对应的子串）是什么。

输入描述

第一行三个整数，分别表示l、r和操作次数。 接下来每一行一个字符c和一个字符串s，意义见题目描述。

输出描述

一行，表示对应的子串。

输入样例1

3 8 4
a ab
a bc
c de
b bbb

输出样例1

bdebbb

提示

1. 数据范围： $l,r \leq min(|S|, 10^{18})$ $r-l+1 \leq 2 \times 10^5$ $\sum|s| \leq 2 \times 10^5$ 所有的字符都只包含小写字母a-z。 其中对于测试点2-7，满足： $r - l + 1 \leq 2000, \sum|s| \leq 2000$。

2. 字符串转换过程: $a \to ab \to bcb \to bdeb \to bbbdebbb$

3. 测试点分布： 输入2−7: $\sum|s|, r-l+1 \leq 2000$ 输入8-15: 无限制。