Флешмоб#4268
Джампінг Джек відповідає за організацію флешмобу. Учасники флешмобу пересуваються містом протягом дня, і частина привабливості цієї групи полягає в тому, що вони збираються разом, щоб виконати свій номер, коли Джек відчує натхнення. Коли натхнення приходить, Джек відправляє текстове повідомлення учасникам, щоб зустрітися на певному перехресті в місті рівно через годину. Вулиці міста пролягають лише з півночі на південь або зі сходу на захід і рівномірно розташовані, утворюючи ідеальну сітку, як аркуш графічного паперу. Через спонтанність Джек хоче мінімізувати незручності і тому вибирає перехрестя, щоб мінімізувати загальну відстань, яку пройдуть учасники флешмобу. На щастя, Джек має місцезнаходження всіх учасників через GPS на їхніх мобільних телефонах. Ваше завдання - знайти місце зустрічі, враховуючи місцезнаходження всіх учасників.
Кожне перехрестя буде задано парою невід'ємних цілих чисел; перша координата - це вулиця зі сходу на захід, а друга координата - вулиця з півночі на південь. Місцезнаходження кожного учасника флешмобу буде перехрестям. Учасники можуть пересуватися лише з півночі на південь або зі сходу на захід між перехрестями.
Наприклад, припустимо, що є учасників флешмобу на місцях , , , та . Тоді, якщо Джек викликає їх усіх на місце , загальна кількість кварталів, які пройдуть учасники флешмобу, буде . Джек не міг би зробити краще - але іноді "найкраще" місце може бути не унікальним.
Вхідні дані для кожного тестового випадку будуть серією цілих чисел на одному або декількох рядках. Перше число, (1 \le n \le 1000), вказує кількість учасників флешмобу. Далі йдуть пар цілих чисел, що вказують місцезнаходження (перехрестя) кожного учасника. Координати місцезнаходження знаходяться в межах від до 10^6, включно. Більше ніж один учасник може бути на одному перехресті. Рядок, що містить , буде після останнього тестового випадку.
Виведіть один рядок для кожного тестового випадку у форматі, наведеному нижче. Упорядкована пара - це координати місця в місті, де загальна відстань, пройдена (в кварталах), є мінімальною. Якщо є більше ніж одне таке місце, виведіть те, що має найменшу першу координату. Якщо є більше ніж одне "найкраще" місце з найменшою першою координатою, виведіть те з них, що має найменшу другу координату. Загальна кількість кварталів, пройдених усіма учасниками флешмобу, слідує за місцем.
Приклад 1