Код замка
Трус, Балбес и Бывалый тщательно готовились к предстоящему делу на протяжении трёх дней. И, как это обычно бывает, в самый последний момент стали известны новые подробности операции. Оказалось, что на складе поставили новый электронный замок.
К счастью, грабители узнали, что код замка можно получить из строки 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' включительно.
Выходные данные
Строка, являющуяся кодом замка.