Смена кластеров отзывов после двух итераций

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

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

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

Расстояние от отзыва до центра называется квадратом евклидова расстояния по известным признакам: d = sum((x_j - c_j)^2), где сумма берётся только по признакам отзыва, не равным NA. Если для некоторого признака в кластере нет ни одного известного значения, соответствующая координата центра сохраняется от предыдущего центра. Если кластер пуст, обе координаты его центра сохраняются от предыдущего центра.

При равенстве расстояний выбирается кластер с меньшим номером.

Формат ввода

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

В следующих n строках даны идентификатор отзыва word, оценка тональности sentiment и оценка технической проблемы issue. Вместо каждого из двух чисел может стоять NA.

В следующих k строках даны две целые координаты начальных центров: sentiment_center и issue_center. Кластеры нумеруются от 1 до k в порядке задания этих строк.

В следующей строке дано целое число q — количество слов в запросе.

В следующих q строках даны идентификаторы отзывов из запроса.

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

Для каждого слова из запроса выведите отдельную строку из трёх значений: идентификатор слова, его метка после первой итерации и его метка после второй итерации.

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

Ограничения

1 <= n <= 4000.

1 <= k <= min(n, 30).

1 <= q <= n.

Идентификатор word состоит из строчных латинских букв, цифр и символа _, его длина от 1 до 20. Все идентификаторы отзывов различны. Каждый идентификатор в запросе встречается среди отзывов.

Каждая числовая оценка отзыва и каждая координата начального центра является целым числом от -1000 до 1000 включительно.

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

Дробные средние центров вычисляются точно. Округление координат центров не выполняется.