Программирование Python алгоритм

Тимофей пишет свою поисковую систему.

Имеется n документов, каждый из которых представляет собой текст из слов. По этим документам требуется построить поисковый индекс. На вход системе будут подаваться запросы. Запрос —– некоторый набор слов. По запросу надо вывести 5 самых релевантных документов.

Релевантность документа оценивается следующим образом: для каждого уникального слова из запроса берётся число его вхождений в документ, полученные числа для всех слов из запроса суммируются. Итоговая сумма и является релевантностью документа. Чем больше сумма, тем больше документ подходит под запрос.

Сортировка документов на выдаче производится по убыванию релевантности. Если релевантности документов совпадают —– то по возрастанию их порядковых номеров в базе (то есть во входных данных).

Формат ввода

В первой строке дано натуральное число n —– количество документов в базе (1 <= n <= 104).

Далее в n строках даны документы по одному в строке. Каждый документ состоит из нескольких слов, слова отделяются друг от друга одним пробелом и состоят из маленьких латинских букв. Длина одного текста не превосходит 1000 символов. Текст не бывает пустым.

В следующей строке дано число запросов —– натуральное число m (1 <= m <=104). В следующих m строках даны запросы по одному в строке. Каждый запрос состоит из одного или нескольких слов. Запрос не бывает пустым. Слова отделяются друг от друга одним пробелом и состоят из маленьких латинских букв. Число символов в запросе не превосходит 100.

Формат вывода

Для каждого запроса выведите на одной строке номера пяти самых релевантных документов. Если нашлось менее пяти документов, то выведите столько, сколько нашлось. Документы с релевантностью 0 выдавать не нужно.

Ограничение по времени 6,5сек

Ограничение по памяти: 128МБ

Примеры ввода:

Пример 1

3

i love coffee

coffee with milk and sugar

free tea for everyone

3

i like black coffee without milk

everyone loves new year

mary likes black coffee without milk

Вывод:

1 2

3

2 1

Пример 2

6

buy flat in moscow

rent flat in moscow

sell flat in moscow

want flat in moscow like crazy

clean flat in moscow on weekends

renovate flat in moscow

1

flat in moscow for crazy weekends

Вывод

4 5 1 2 3