Обновление центров тренировок

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

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

Для тренировки с координатами \((x, y)\) и центра с координатами \((a, b)\) используется квадрат евклидова расстояния: \(d^2=(x-a)^2+(y-b)^2\). Тренировка относится к центру с наименьшим значением \(d^2\). Новая координата центра равна среднему арифметическому соответствующих координат всех тренировок, отнесённых к этому центру.

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

Формат ввода

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

В следующих \(k\) строках записаны по два целых числа: длительность и пульс начального центра. Центры пронумерованы от 1 до \(k\) в порядке этих строк.

В следующих \(n\) строках записаны по два значения: длительность тренировки и её средний пульс. Вместо любого из значений может стоять символ -, обозначающий пропуск.

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

Выведите \(k\) строк в порядке начальных центров. В каждой строке выведите две координаты нового центра: длительность и пульс.

Каждую координату выводите ровно с двумя знаками после точки.

Ограничения

\(1 \le n \le 2000\).

\(1 \le k \le 20\).

\(k \le n\).

Длительность начального центра и заполненной тренировки — целое число от 1 до 600.

Пульс начального центра и заполненной тренировки — целое число от 40 до 240.

Каждое поле во входных строках имеет длину от 1 до 3 символов, кроме символа -, имеющего длину 1.

Каждая строка тренировки содержит ровно два поля.

Полностью заполненных тренировок не меньше \(k\), и после распределения по описанному правилу ни одна группа не остаётся пустой.