Задача A. TF-IDF ≡

Условие

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

tf(t,d) = n_t∑_k n_k

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

idf(t,D) = log₁₀|D||{ d_i ∈ D ∣ t ∈ d_i }|

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

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

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

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

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

Ограничения

1 ≤ N, W,K ≤ 10⁵.

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

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

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