Задача C. Арифметическая прогрессия

Автор:Жюри ВКОШП 2010   Ограничение времени:2 сек
Входной файл:arithm.in   Ограничение памяти:256 Мб
Выходной файл:arithm.out  

Условие

Однажды Петя узнал очень важную последовательность из n чисел. Тщательно проанализировав ее, он обнаружил, что она является арифметической прогрессией. Чтобы не забыть он записал ее элементы на n карточках.

Но затем случилась неприятность. Не зная всю важность этой последовательности, его брат Вовочка взял еще n карточек и написал на них произвольные числа, а потом перемешал все 2 n карточек.

Теперь Петя хочет восстановить исходную последовательность по этим карточкам. К сожалению возможно, что это можно сделать несколькими способами, но Петю устроят любые n чисел, образующие арифметическую прогрессию.

Петя не может сделать это вручную, поэтому обратился к вам за помощью.

Напомним что последовательность a1, a2, …, an называется арифметической прогрессией, если ai = ai1 + d для всех i от 2 до n и некоторого d. Число d называется разностью арифметической прогрессии.

Формат входного файла

В первой строке входного файла находится целое число n (1 ≤ n ≤ 100 000). В следующей строке находится 2 n целых чисел по модулю не превосходящих 109 — числа, написанные на карточках, перечисленные в произвольном порядке. Гарантируется, что можно выбрать n из них так, чтобы они образовывали арифметическую прогрессию.

Формат выходного файла

В первой строке выходного файла выведите a1 и d — первый элемент и разность найденной арифметической прогрессии. Если d = 0, число a1 должно встречаться среди заданных чисел n раз.

Если существует несколько решений, выведите любое.

Примеры тестов

Входной файл (arithm.in) Выходной файл (arithm.out)
1
3
8 7 1 5 4 3
1 3

0.036s 0.008s 15