Цензура (Золото)#11183

Цензура (Золото)

1 секунда

128 мегабайтів

Складна

Фермер Джон придбав для своїх корів підписку на журнал $G oo d H oo v es k ee p in g$ Good~Hooveskeeping, щоб їм було що почитати, поки вони чекають у корівнику під час дійки. На жаль, в останньому випуску міститься досить недоречна стаття про те, як приготувати ідеальний стейк, і ФД хотів би, щоб його корови її не побачили. Очевидно, журналу не завадив би більш ретельний редакторський контроль.

ФД витягнув весь текст із журналу в рядок $s$ довжини не більше $1 0^{5}$ 10^5 символів. Крім того, у нього є список із $n$ заборонених слів $t_{1}, t_{2}, \dots, t_{n}$ t_1, t_2, \ldots, t_n, які він хоче видалити з $s$ .

Щоб піддати текст цензурі, ФД багаторазово знаходить найраніше входження будь-якого забороненого слова в $s$ , де «найраніше» означає входження з найменшим початковим індексом, і видаляє це входження з $s$ . Він продовжує цей процес до тих пір, поки в $s$ не залишиться жодного забороненого слова. Зверніть увагу, що видалення одного забороненого слова може створити нове входження іншого забороненого слова, якого раніше не існувало.

ФД зауважує, що заборонені слова мають наступну властивість: жодне заборонене слово не є підрядком іншого забороненого слова. Зокрема, це гарантує, що заборонене слово з найранішим початковим індексом у $s$ визначається однозначно.

Допоможіть ФД визначити, яким буде вміст рядка $s$ після завершення процесу цензури.

Вхідні дані

У першому рядку міститься рядок $s$ . У другому рядку міститься ціле число $n$ — кількість заборонених слів. У наступних $n$ рядках містяться рядки $t_{1}, t_{2}, \dots, t_{n}$ t_1, t_2, \ldots, t_n.

Кожен рядок складається лише зі малих англійських букв (з діапазону $a \dots z$ ), а сумарна довжина всіх заборонених слів не перевищує $1 0^{5}$ 10^5.

Вихідні дані

Виведіть рядок $s$ після завершення всіх видалень. Гарантується, що в процесі видалення рядок $s$ не стане порожнім.

Приклади

Приклад 1