题目描述

有一个字符串 $s$，初始 $s$ 为单独一个字符 a。

依次进行 $n$ 次操作，第 $i$ 次操作中给定一个字符 $c_i$ 和一个字符串 $t_i$，表示将 $s$ 中所有字符 $c_i$ 同时替换为字符串 $t_i$。

另给定 $l,r$，求 $n$ 次操作之后 $s_l,\dots,s_r$。

输入格式

第一行，三个整数 $l,r,n$。

接下来 $n$ 行，每行依次是一个字符 $c_i$ 和一个字符串 $t_i$，中间由空格分开。

输出格式

一行，$r-l+1$ 个字符，依次表示 $s_l,\dots,s_r$。

样例

样例输入 1

3 8 4
a ab
a bc
c de
b bbb

样例输出 1

bdebbb

数据范围

对于 $100\%$ 的数据，$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$，本题涉及的所有字符均为小写英文字母。

$\text{Subtask 1}(50\%):n\le 2000,r-l+1\le 2000$。

$\text{Subtask 2}(50\%):$ 无特殊限制。