eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Код замка

Код замка

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Трус, Балбес и Бывалый тщательно готовились к предстоящему делу на протяжении трёх дней. И, как это обычно бывает, в самый последний момент стали известны новые подробности операции. Оказалось, что на складе поставили новый электронный замок.

К счастью, грабители узнали, что код замка можно получить из строки S, состоящей из символов 'a'-'z', и массива строк conversions, каждая строка в котором имеет вид "s1-s2", где s1 и s2 - строки из символов 'a'-'z'.

Чтобы из строки S получить код замка, необходимо просмотреть все элементы массива conversions в порядке возрастания их индексов и для каждого элемента "s1-s2" проделать следующие действия:

  • если строка S содержит хотя бы одно вхождение строки s1 в качестве подстроки, то необходимо заменить в S первое (самое левое) такое вхождение на строку s2;

  • если же строка S не содержит ни одного вхождения строки s1 в качестве подстроки, то необходимо добавить строку s2 в конец строки S.

Так как до начала операции осталось совсем мало времени, а код вручную определять очень долго, грабители обратились сначала за помощью к программистам, участвующим в конкурсе "Операция Ы.MEDIUM", а теперь и к участникам Новогоднего марафона под Новый Год 2011.

Входные данные

В первой строке задана строка S. Во второй - количество элементов N в массиве conversions. В последующих строках задан сам массив conversions.

Строка S состоит из от 1 до 50 символов 'a'..'z' включительно. Массив conversions содержит от 1 до 50 элементов включительно. Каждый элемент массива conversions имеет вид "s1-s2", где s1 и s2 - строки, состоящие из от 1 до 10 символов 'a'..'z' включительно.

Выходные данные

Строка, являющуяся кодом замка.

Пример

Входные данные #1
testthebest
3
test-best
the-ofthe
mode-code
Выходные данные #1
bestofthebestcode