Поиск наблюдения птиц по TF-IDF

В журнале парка хранятся краткие текстовые описания наблюдений за птицами. Некоторые записи не содержат текста: в этом случае строка записи равна одному символу -.

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

Для слова w в документе d его частота равна tf(w,d) = c(w,d) / L(d), где c(w,d) — число вхождений слова, а L(d) — число слов в документе. Пусть df(w) — число документов, в которых слово встречается хотя бы раз. Тогда idf(w) = ln(n / df(w)), где ln — натуральный логарифм. Координата TF-IDF-вектора равна tf(w,d) * idf(w). Близость документа d и запроса q вычисляется по формуле S(d,q) = (v(d) · v(q)) / (||v(d)|| * ||v(q)||). Слова запроса, отсутствующие во всех документах, имеют нулевую координату. Если хотя бы один из двух векторов имеет нулевую длину, его близость считается равной нулю.

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

Ответ является целым числом, округление не применяется.

Формат ввода

В первой строке дано целое число n — число документов.

В следующих n строках даны тексты документов в порядке их номеров от 1 до n. Текст - обозначает отсутствующее описание наблюдения.

В последней строке дан текст поискового запроса.

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

Выведите один номер документа с наибольшей косинусной близостью TF-IDF-вектора к запросу.

Ограничения

1 ≤ n ≤ 4000.

Каждый непустой документ содержит от 1 до 20 слов. Документ без текста задаётся строкой -.

Запрос содержит от 1 до 20 слов и не равен -.

Длина каждого слова — от 1 до 20 строчных латинских букв.

Длина каждой строки документа и строки запроса не превышает 420 символов.