Жанр фильма по ближайшим карточкам

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

Для нового фильма с идентификатором TARGET нужно предсказать один жанр методом взвешенных ближайших соседей. В технической карточке указаны длительность в минутах и оценка критиков от 0 до 100. Значение NA означает, что соответствующий параметр неизвестен.

Для размеченного фильма i рассматриваются только параметры, известные и у фильма i, и у TARGET. Расстояние Манхэттена равно d_i = сумма |a_j - b_j| по всем таким параметрам j. Вес фильма i равен w_i = 1 / d_i. Выбираются k фильмов с наименьшими расстояниями, после чего для каждого жанра суммируются веса выбранных фильмов этого жанра. Ответом является жанр с наибольшей суммой весов.

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

Формат ввода

В первой строке даны два целых числа n и k — число размеченных фильмов и число соседей.

В следующих n строках находится первая таблица. Каждая строка содержит идентификатор фильма movie_id и его жанр genre.

В следующих n + 1 строках находится вторая таблица. Каждая строка содержит идентификатор фильма movie_id, длительность duration и оценку критиков critics_score. Вместо числового значения длительности или оценки может стоять строка NA.

Во второй таблице ровно одна строка имеет идентификатор TARGET. Все остальные её идентификаторы совпадают с идентификаторами из первой таблицы, каждый встречается ровно один раз.

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

Выведите один жанр, предсказанный для фильма TARGET.

Ограничения

1 <= n <= 3999.

1 <= k <= n.

Идентификатор размеченного фильма состоит из латинской буквы M и от 1 до 15 десятичных цифр. Его длина не превосходит 16 символов.

Жанр — одно из слов action, comedy, drama, fantasy. Длина жанра не превосходит 7 символов.

Если значение не равно NA, то 1 <= duration <= 300 и 0 <= critics_score <= 100.

Во второй таблице не более 4000 строк. У TARGET известны оба технических параметра. Для каждого размеченного фильма имеется хотя бы один общий с TARGET известный параметр, а вычисленное расстояние до TARGET не равно нулю.