Поиск смены по показаниям станции

Метеостанция сохраняет показания температуры за каждую смену. Одно показание записывается целым числом в десятых долях градуса. Иногда датчик не передаёт значение, тогда вместо него записывается NA.

Каждая смена рассматривается как документ, а целые показания температуры рассматриваются как слова документа. В конце входа дана последовательность показаний ЗАПРОСА. Требуется найти смену, наиболее близкую к запросу по TF-IDF и косинусному сходству.

Значения NA полностью игнорируются: они не являются словами документа и не участвуют в длине документа. Для целого значения v обозначим через c(d, v) число его вхождений в смену d, через L(d) число числовых показаний в смене, а через df(v) число смен, в которых значение v встречается хотя бы один раз. Используется сглаженный TF-IDF: tf(d, v) = c(d, v) / L(d), idf(v) = ln((n + 1) / (df(v) + 1)) + 1, w(d, v) = tf(d, v) * idf(v). Для запроса формулы те же, причём df(v) = 0, если значение встречается только в запросе. Сходство смены d и запроса q равно sum_v(w(d, v) * w(q, v)) / (sqrt(sum_v(w(d, v)^2)) * sqrt(sum_v(w(q, v)^2))), где суммирование идёт по всем целым значениям, встретившимся во входе.

Нужно вывести номер смены с наибольшим сходством. Если наибольшее значение достигается у нескольких смен, выводится смена с меньшим номером. Округление не применяется, так как выводится целое число.

Формат ввода

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

В следующих n строках описаны смены. Каждая строка начинается с целого числа k, после которого записаны k токенов показаний. Каждый токен имеет вид целого числа или NA.

В последней строке записан ЗАПРОС: сначала целое число q, затем q токенов показаний в том же формате.

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

Выведите одно целое число — номер наиболее близкой к ЗАПРОСУ смены. Нумерация смен начинается с 1.

Ограничения

1 <= n <= 4000.

1 <= k <= 30, 1 <= q <= 30.

Каждое числовое показание находится в диапазоне от -500 до 500 включительно.

Длина токена числового показания не превосходит 4 символов, токен пропуска имеет длину 2 и равен NA.

В каждой смене есть хотя бы одно числовое показание. В ЗАПРОСЕ есть хотя бы одно числовое показание.