Преобразователь строк

Преобразователь строк - это специальная компьютерная программа. Она получает на вход строку S и набор правил преобразования строки. Каждое из правил имеет вид c₁c₂ → E, где c₁ и c₂ - маленькие буквы английского алфавита. Символом E здесь обозначена пустая строка. При этом каждый символ присутствует не более, чем в одном правиле.

Преобразователь строк работает по шагам. За один шаг он находит в текущей строке подстроку, совпадающую с правой частью одного из правил, после чего эта подстрока удаляется из текущей строки (этот процесс называется применением правила). Этот процесс продолжается до тех пор, пока существует правило, которое можно применить. Строка, которая остается к моменту, когда нельзя применить никакое правило, считается результатом T работы преобразователя строк.

Пусть, например, набор правил таков: {ab → E, cd → E}, а исходная строка S = aabbccdba. Тогда работа преобразователя будет выглядеть так: aabbccdba → abccdba → ccdba → cba, и результатом T работы преобразователя будет строка cba.

Ваша задача состоит в том, чтобы написать программу, моделирующую работу преобразователя строк с заданным набором правил на заданной строке S.

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

Первая строка входного файла INPUT.TXT содержит целое число n (0 ≤ n ≤ 13) - количество правил. Далее идут n строк, каждая из которых описывает одно из правил. Гарантируется, что каждая из маленьких букв английского алфавита присутствует не более, чем в одном правиле.

Последняя, (n+2)-ая строка входного файла содержит исходную строку S. Она не пуста и состоит только из маленьких букв английского алфавита. Длина S не превосходит 100000.

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

В выходной файл OUTPUT.TXT выведите строку T - результат работы преобразователя на строке S.

Примеры

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]