Задача G. Топики ≡

Условие

Преподаватель английского языка готовится к проведению контрольной работы. У него имеется словарь из N изученных школьниками слов и номер темы, соответствующей каждому слову. Слово может встречаться в словаре несколько раз с разными темами — это значит, что оно относится ко всем этим темам. Слова состоят только из латинских букв, заглавные и строчные буквы не отличаются. Все остальные символы, кроме латинских букв, считаются разделителями.

Кроме того, имеется P английских предложений. Каждое предложение состоит из одного или более слов. Между словами имеются произвольные последовательности разделителей, например first. :second third,,,,fourth. Предложение считается относящимся к i-й теме, если слов на эту тему в нём больше, чем на какую-либо другую. Если самые часто встречающиеся в предложении темы имеют одинаковую частоту, либо если в предложении вообще не встречается ни одного слова из словаря, то тема такого предложения считается неопределёной.

Требуется для каждого предложения вывести номер его темы либо 0, если тема не определена.

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

3 6
a 1
b 2
c 3
a b c
a a b
a B b
c-a == c
d e f
This is a table.

0 1 2 3 0 1