Изменение меток кластеров чеков

Сеть супермаркетов описывает каждый чек двумя признаками: суммой покупки и количеством товаров. Для части чеков один из признаков неизвестен и записан как -1.

Перед кластеризацией все пропуски заменяются средним арифметическим известных значений того же признака среди всех чеков. Если для некоторого признака все значения пропущены, каждый его пропуск заменяется числом 0.

Нужно выполнить две итерации метода k-means для двух кластеров. Начальные центры кластеров даны во входных данных. На каждой итерации чек относится к ближайшему центру по квадрату евклидова расстояния: d((x, y), (a, b)) = (x - a)^2 + (y - b)^2. Затем каждый непустой кластер заменяется средним арифметическим координат всех чеков этого кластера. Если кластер оказался пустым, его центр не изменяется.

Сначала выполняется распределение чеков по начальным центрам и пересчёт центров. Затем чеки распределяются по пересчитанным центрам. Требуется определить, изменилась ли хотя бы одна метка, и вывести метки после второго распределения.

При равенстве расстояний чек относится к кластеру с меткой 1.

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

Формат ввода

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

Во второй строке даны два целых числа c1x c1y — координаты начального центра кластера 1.

В третьей строке даны два целых числа c2x c2y — координаты начального центра кластера 2.

В следующих n строках даны два целых числа x y — сумма чека и количество товаров. Значение -1 означает пропуск соответствующего признака.

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

В первой строке выведите CHANGED, если метка хотя бы одного чека после второго распределения отличается от его метки после первого распределения. Иначе выведите UNCHANGED.

Во второй строке выведите n меток чеков после второго распределения через пробел.

Ограничения

1 ≤ n ≤ 4000.

Координаты начальных центров удовлетворяют 0 ≤ c1x, c2x ≤ 1000000 и 0 ≤ c1y, c2y ≤ 10000.

Для каждого чека x равно -1 или целому числу от 0 до 1000000.

Для каждого чека y равно -1 или целому числу от 0 до 10000.

Хотя бы один кластер может оказаться пустым. Деления на ноль при замене пропусков не происходит: если известных значений признака нет, используется число 0.