Беси работает в текстовом редакторе miV! Его функция "найти и заменить"
позволяет ей заменить все вхождения маленькой латинской буквы \(c\) на непустую строку
из маленьких латинских букв \(s\). Например, дана строка "\(\texttt{ball}\)".
Если Беси выберет в качестве \(c\) символ 'l' а в качестве строки \(s\) "\(\texttt{na}\)",
данная строка трансформируется в "\(\texttt{banana}\)".
Беси начинает со строки "\(\texttt{a}\)" и трансформирует её используя некоторое
количество операций «найти и заменить» и получает финальную строку \(S\). Поскольку
\(S\) может быть большой, она хочет узнать по заданным \(l\) и \(r\)
\(1\le l\le r\le \min(|S|,10^{18})\), чему равно \(S_{l\dots r}\) - подстрока S с позиции \(l\)
по позицию \(r\) включительно.
Гарантируется, что сумма \(|s|\) по всем операциям не более \(2\cdot 10^5\), и что
\(r-l+1\le 2\cdot 10^5\).
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит
\(l\),
\(r\) и количество операций.
Каждая из последующих строк описывает одну операцию и содержит \(c\) и \(s\)
для этой операции. Все символы в интервале от 'a' до 'z'.
ФОРМАТ ВЫВОДА (на экран / stdout):
Выведите строку \(S_{l\dots r}\) на одной строке.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 8 4
a ab
a bc
c de
b bbb
|
bdebbb
|