Классификация поездки велопроката

В городской системе велопроката поездки относятся к одному из тарифных сегментов. Для завершённых поездок известны средняя длительность в минутах, расстояние в десятых долях километра и сегмент.

Для новой поездки требуется определить сегмент методом взвешенных ближайших соседей. В некоторых строках одна из характеристик отсутствует и записана как NA.

Для двух поездок расстояние вычисляется только по характеристикам, известным у обеих поездок. Если таких характеристик q, используется расстояние

d = sqrt(((x1-y1)^2 + ... + (xq-yq)^2) / q).

Сначала выбираются k строк с наименьшими расстояниями. При равенстве расстояний раньше выбирается строка, которая раньше встретилась во входных данных. Голос строки с расстоянием d > 0 за её сегмент равен 1 / d.

Если среди выбранных k строк есть поездки с нулевым расстоянием, учитываются только они: каждая такая строка даёт своему сегменту голос 1, а остальные выбранные строки не учитываются. Для каждого сегмента суммируются голоса. Перед сравнением суммы голосов округляются до 10 знаков после точки по правилу округления к ближайшему, а при ровно половинном значении — в большую сторону по модулю.

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

Формат ввода

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

В следующих n строках записаны три значения: duration distance segment, где duration — средняя длительность поездки, distance — расстояние, segment — метка тарифного сегмента.

В последней строке записаны два значения duration distance для новой поездки.

Значение отсутствующей числовой характеристики обозначается строкой NA.

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

Выведите одну строку — метку сегмента новой поездки.

Ограничения

1 <= n <= 4000.

1 <= k <= n.

Каждая известная длительность и длительность новой поездки — целое число от 0 до 1440 или NA.

Каждое известное расстояние и расстояние новой поездки — целое число от 0 до 3000 или NA.

В каждой строке известной поездки указана хотя бы одна числовая характеристика.

Метка segment состоит из строчных латинских букв, её длина от 1 до 12.

Для каждой известной поездки существует хотя бы одна характеристика, известная также у новой поездки. Поэтому расстояние определено для всех n строк.