Фермер Джон купил подписку журнала Good Hooveskeeping для своих коров. К сожалению, последний номер содержит неподходящую статью - как приготовить бифштекс. ФД не хочет, чтобы его коровы её читали.
ФД взял текст журнала, создал строку s длиной не более чем 10^5
символов. У него есть список слов t[1]
, t[2]
, ..., t[n]
, которые он хочет удалить из s. Поэтому ФД находит ближайшее вхождение слова из списка t (то есь с наименьшим индексом) и удаляет его из s. Затем он продолжает это процесс опять, пока в s не останется слов из t. Заметим, что удаление слова может создавать новое вхождение слова из t, которое не существовало ранее.
ФД заметил, что слова из списка t обладают таким свойством, что никакое из них не является подстрокой другого слова из t. В частности, это означает, что ранее вхождение слова из t в s всегда определено однозначно. Пожалуйста, помогите ФД определить финальное содержание строки s.
Первая строка содержит s. Вторая строка содержит n - количество удаляемых слов. Последующие n строк содержат строки t[1]
, t[2]
, ..., t[n]
. Каждая строка содержит только маленькие латинские буквы (a..z) и суммарная длина всех строк не превысит 10^5
.
Строка s после всех удалений. Гарантируется, что s не станет пустой.