Задача №113811. ЗигЗаг
Зиг и Заг играют в игру. Зиг говорит букву, а Заг — слово. Но слово не простое, а такое, что начинается с буквы Зига. Но и это не всё. Слово это должно быть в специальном списке слов, а из всех таких должно оно быть произнесено наименьшее число раз. А из всех слов из списка, начинающихся с буквы Зига, которые были произнесены минимальное число раз Заг должен взять лексикографический минимальное. Загу сложно. Помогите Загу.
Вам дан список S из k разрешённых слов. Так же вам даны буквы Зига за первые n ходов. На каждую из этих ходов найдите слово, которое Заг должен сказать.
В первой строке ввода содержится 2 числа k и n ( 1 ≤ k ≤ 10 5 , 1 ≤ n ≤ 10 5 ) — число слов в списке и число ходов.
В следующих k строках даны различные слова из списка, по одному в строке. Каждое из слов имеет длину не более 21 символа.
В следующих n строках даны буквы Зига, по одной в строке. Буквы даны в том порядке, в котором Зиг своими ходами их называет.
Выведите n строк, в i -й — то слово, которое Заг должен ответить на ход Зига. Гарантируется, что Заг всегда может сделать ход.
Решения, работающие при n ≤ 500 и k ≤ 500 будут оцениваться в 60 балов.
4 5 zagreb split zadar sisak z s s z z
zadar sisak split zagreb zadar
5 3 london rim pariz moskva sarajevo p r p
pariz rim pariz
1 3 zagreb z z z
zagreb zagreb zagreb