该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小S有一个带有魔法的字符串，为什么有魔法呢，是因为它可以自我增殖。 最开始的时候这个魔法串只会有一个字母 a , 在每一天这个魔法串都会针对自己的某种字符 将自身全部的这种字符变为某一个字符串 s ，例如原本的字符串为 "abcabc" 若把其中的 'a' 替换为字符串 "aabbcc" 则字符串变为 "aabbccbcaabbccbc"。 这个字符串太不可控了，谁也不知道它最终会变成什么恐怖的样子，于是小S就只能请教大预言家 Lu Chen 先生，Lu Chen 告诉小S，这个魔法串一共只会增殖 $n$ 天，你并不需要掌握字符串最终 的全部样子，只需要知道 在最终的字符串中 $l$ 到 $r$ 这个区间内的字符串，你就能掌控这个魔力串了。 小S 希望你帮忙降伏这个魔法串 ！字符串序号从 1 开始

输入描述

第一行输入包括三个正整数，分别表示 $l$ , $r$ , $n$ 。 接下来 $n$ 行，每行一个字符 $c$ 和一个字符串 $s$ , 表示每天的增殖情况。

输出描述

输出 最终字符串 $l$ 到 $r$ 区间内的所有字符。

样例描述

输入1

5 9 3
a abc
b aca
c aaa

输出1

aaaaa

输入2

1 20 6
a ab
a bcd
c bbc
d abcda
a bcabc
b acacba

输出2

acacbaacacbaacacbaca

样例解释

在第一组样例中 ：

• a -> abc
• abc -> aacac
• aacac -> aaaaaaaaa

在第二组样例中 ：

• a -> ab
• ab -> bcdb
• bcdb -> bbbcdb
• bbbcdb -> bbbcabcdab
• bbbcabcdab -> bbbcbcabcbcdbcabcb
• bbbcbcabcbcdbcabcb -> acacbaacacbaacacbacacacbacaacacbacacacbacdacacbacaacacbacacacba

数据范围描述

• 对于 测试点 2 - 7 满足：$r - l + 1 \le 2000 , \sum |s| \le 2000$
• 对于 100%的数据 满足 ：$l , r \le min(|S|,10^{18})$ , $r - l + 1 \le 2 * 10^5$ , $\sum |s| \le 2 * 10^5$