Перераспределение квартир по расходу электричества

Управляющая компания распределила квартиры дома на группы по суточному расходу электричества. Для каждой квартиры известен её прежний номер группы и показание счётчика за сутки.

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

Расстояние между показанием x и центром группы c равно евклидову расстоянию в одномерном случае: d(x, c) = |x - c|. Строка NA вместо показания означает, что счётчик не передал данные. Такие квартиры не участвуют в вычислении центров и не перераспределяются. Запрошенная квартира всегда имеет известное показание.

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

Формат ввода

В первой строке даны два целых числа n и k: число квартир и число групп.

В следующих n строках даны три значения: номер квартиры apartment_id, показание daily_kwh и прежний номер группы old_cluster.

Показание daily_kwh является целым числом либо строкой NA.

В последней строке дано одно целое число query_apartment_id — номер квартиры, для которой требуется определить новую группу.

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

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

Дробная часть не выводится, так как ответом является целый номер группы.

Ограничения

1 ≤ n ≤ 2000.

1 ≤ k ≤ min(n, 50).

1 ≤ apartment_id, query_apartment_id ≤ 10^9. Номера квартир во входе различны.

0 ≤ daily_kwh ≤ 200000, если вместо показания не указано NA.

1 ≤ old_cluster ≤ k.

Запрошенная квартира присутствует среди n строк и имеет числовое показание.

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