Код замка
Трус, Балбес та Бувалий ретельно готовались до майбутньої справи протягом трьох днів. І, як це звичайно буває, у самий останній момент стали відомі нові подробиці операції. Виявилось, що на складі поставили новий електроний замок.
На щастя, грабіжники взнали, що код замка можна отримати з рядкаи 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' включно.
Вихідні дані
Рядок, який є кодом замка.