Новые центры графиков кормления

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

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

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

Если расстояния до нескольких центров одинаковы, животное относится к центру, который раньше указан во второй таблице.

Формат ввода

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

Следующие n строк образуют первую таблицу. В каждой строке записаны animal_id, morning и evening: идентификатор животного, минута первого кормления и минута последнего кормления. Вместо неизвестного времени записывается символ -.

Следующие k строк образуют вторую таблицу. В каждой строке записаны center_id, morning_center и evening_center: идентификатор центра и его две начальные координаты.

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

Выведите k строк в порядке центров из второй таблицы. В каждой строке выведите идентификатор центра, новую координату первого кормления и новую координату последнего кормления.

Каждую координату выводите ровно с двумя знаками после точки. При округлении третья цифра после точки 5 или больше увеличивает второй знак после точки на 1.

Ограничения

1 ≤ n ≤ 2000.

1 ≤ k ≤ n.

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

Каждое известное значение morning, evening, morning_center, evening_center — целое число от 0 до 1440.

У каждого животного известно хотя бы одно время кормления.

Для каждого центра после распределения найдётся хотя бы одно животное группы с известным первым временем и хотя бы одно животное группы с известным последним временем. Поэтому пустых групп и деления на ноль не возникает.