Флешмоб
Джампинг Джек отвечает за организацию флешмоба. Участники флешмоба перемещаются по городу в течение всего дня, и одна из особенностей этой группы заключается в том, что они собираются вместе, чтобы выступить, когда Джек почувствует вдохновение. Когда это происходит, Джек отправляет сообщение участникам, чтобы они встретились на определенном перекрестке в городе ровно через час. Улицы города проходят только с севера на юг или с востока на запад и равномерно расположены, образуя идеальную сетку, как лист миллиметровой бумаги. Из-за спонтанности Джек хочет минимизировать неудобства и поэтому выбирает перекресток, чтобы минимизировать общее расстояние, которое должны пройти участники флешмоба. К счастью, у Джека есть данные о местоположении всех участников через GPS на их мобильных телефонах. Ваша задача — найти место встречи, учитывая местоположения всех участников.
Каждый перекресток задается парой неотрицательных целых чисел; первая координата — это улица восток-запад, а вторая координата — улица север-юг. Местоположение каждого участника флешмоба — это перекресток. Участники могут перемещаться только с севера на юг или с востока на запад между перекрестками.
Например, предположим, что есть 5 участников на местоположениях (3, 4), (0, 5), (1, 1), (5, 5) и (5, 5). Тогда, если Джек соберет их всех в местоположении (3, 5), общее количество кварталов, пройденных участниками, будет 14. Джек не смог бы сделать лучше — но иногда 'лучшее' местоположение может быть не уникальным.
Входные данные
Ввод для каждого теста будет серией целых чисел на одной или нескольких строках. Первое число, n (1 ≤ n ≤ 1000), указывает количество участников. Далее следуют n пар целых чисел, указывающих местоположение (перекресток) каждого участника. Координаты местоположения находятся в пределах от 0 до 10^6 включительно. Более одного участника может находиться на одном перекрестке. Строка, содержащая 0, будет следовать за последним тестом.
Выходные данные
Выведите одну строку для каждого теста в формате, указанном ниже. Упорядоченная пара — это координаты местоположения в городе, где общее расстояние, пройденное (в кварталах), минимально. Если существует более одного такого местоположения, выведите то, у которого наименьшая первая координата. Если существует более одного 'лучшего' местоположения с наименьшей первой координатой, выведите то из них, у которого наименьшая вторая координата. Общее количество кварталов, пройденных всеми участниками, следует за местоположением.