Редактор с левыми заменами

В кружке по робототехнике есть «исполнитель-редактор». Он умеет менять в строке один фрагмент на другой по строгим правилам.

Тебе дана строка S из строчных латинских букв и k правил вида u v.

Правила применяются строго по очереди: сначала первое правило — пока в текущей строке встречается подстрока u, редактор находит САМОЕ ЛЕВОЕ вхождение u и заменяет его на v. Когда вхождений u больше нет, редактор переходит ко второму правилу, затем к третьему и так далее до k-го.

Важно: для каждого правила выполняется |v| < |u|. Поэтому после каждой замены строка строго укорачивается, и процесс всегда заканчивается.

Выведи строку, которая получится после применения всех k правил. Если в итоге строка стала пустой, выведи пустую строку.

Формат ввода:

• Первая строка: строка S (только строчные латинские буквы).
• Вторая строка: целое число k.
• Следующие k строк: по два слова u и v (строчные латинские буквы), разделённые пробелом.

Формат вывода:

• Одна строка — результат работы редактора.

Ограничения:

• 1 ≤ |S| ≤ 2000
• 1 ≤ k ≤ 5
• 1 ≤ |v| < |u| ≤ 5

Пример Ввод: ababa 1 aba a

Вывод: a