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

Автор:А. Кленин   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

Входной файл содержит числа N P за которыми идут N строк вида wi ti, где wi — слово, ti — номер темы, а затем P строк, каждая из которых содержит одно предложение.

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

В выходной файл должно быть выведено P чисел — темы предложений.

Ограничения

1 ≤ N ≤ 1000, 1 ≤ P ≤ 2000, 1 ≤ ti ≤ 10000, длина каждого слова и каждого предложения не превосходит 255 символов,

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

Входной файл (input.txt) Выходной файл (output.txt)
1
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

0.034s 0.007s 15