Бесі працює у текстовому редакторі 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 \).

Формат вхідних даних

Перший рядок містить \(l\), \(r\) та кількість операцій.

Кожен з наступних рядків описує одну операцію і містить \(c\) та \(s\) для цієї операції. Усі символи в інтервалі від 'a' до 'z'.

Формат вихідних даних

Виведіть рядок \(S_{l\dots r}\).

Приклад вхідних даних

3 8 4
a ab
a bc
c de
b bbb

Приклад вихідних даних

bdebbb

Вихідний рядок трансформувався таким чином: \(\texttt{a} \rightarrow \texttt{ab} \rightarrow \texttt{bcb} \rightarrow \texttt{bdeb} \rightarrow \texttt{bbbdebbb}\)

ОЦІНЮВАННЯ:

• Тести 2-7: \(\sum |s|, r-l+1\le 2000\)
• Тести 8-15: Немає додаткових обмежень.