Задача A. TF-IDF

Входной файл:Стандартный вход   Ограничение времени:10 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб

Условие

Требуется реализовать TF-IDF векторайзер по заданному корпусы D содержащему N предложений и примерить его к K предложениям.

tf(t,d) = ntk nk

Где nt есть число вхождений слова t в предложение, а в знаменателе — общее число слов в данном предложении.

idf(t,D) = log10|D||{ di∈ D∣ t∈ di }|

|D| — число документов в коллекции; |{ di ∈ D ∣ t ∈ di }| — число документов из коллекции D, в которых встречается t.

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

Первая строка содержит N - количество предложений в корпусе D. Далее следует N строк описывающих предложения корпуса, первое число в строке m количество слов в предложении, далее идёт m слов, являющиеся результатом токенизации предложения из корпуса D. Далее следует W - количество уникальных слов в корпусе D. Следующие W строк содержат слова и их индексы. Далее следует K запросов, такого же формата как и предложения корпуса D.

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

Для каждого запроса из требуется вывести значения TF-IDF для каждого слова (сначала индекс слова, потом значение TF-IDF), в порядке увеличения индексов с точность до 5ти знаков после запятой.

Ограничения

1 ≤ N, W,K ≤ 105.

Суммарная длина всех слов в тест не превосходи 106. Во всех предложениях запросов все слова содержатся в корпусе.

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

Стандартный вход Стандартный выход
1
4
4 a a a a
4 a b c d
4 b c d e
4 c d e f
6
a 1
b 2
c 3
d 4
e 5
f 6
2
5 a b c d a
3 a a a
4
1 0.120412
2 0.060206
3 0.0249877
4 0.0249877
1
1 0.30103

0.088s 0.017s 13