D. Две прогрессии
ограничение по времени на тест
1 second
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Арифметическая прогрессия — это такая непустая последовательность чисел, в которой разница между любыми двумя последовательными членами равна константе, называемой разностью прогрессии. Например, последовательность 3, 7, 11, 15 — арифметическая прогрессия. Из определения следует, что любые последовательности длины 1 или 2 — арифметические, а длины 0 — не арифметические.

Задана последовательность различных целых чисел a1, a2, ..., an. Требуется разбить ее на две арифметические прогрессии или определить, что это невозможно сделать. При разбиении каждый член заданной последовательности должен быть отнесен в одну из двух прогрессий, при этом относительный порядок чисел остается неизменным. Разбиение — это обратная операция к слиянию последовательностей.

Входные данные

В первой строке записано целое положительное число n (2 ≤ n ≤ 30000), n — длина заданной последовательности. Вторая строка содержит элементы заданной последовательности a1, a2, ..., an ( - 108 ≤ ai ≤ 108). Элементы последовательности — различные целые числа.

Выходные данные

Выведите искомые арифметические прогрессии, по одной на строке. Прогрессии можно располагать в любом порядке. Каждая прогрессия должна содержать хотя бы одно число. Если решения не существует, то выведите «No solution» (без кавычек) в единственную строку выходного файла. Если решений несколько, выведите любое из них.

Примеры
Входные данные
6
4 1 2 7 3 10
Выходные данные
1 2 3 
4 7 10
Входные данные
5
1 2 3 -2 -7
Выходные данные
1 2 3 
-2 -7
Примечание

Во втором примере возможен другой вариант ответа (число 3 может быть отнесено во вторую прогрессию): 1, 2 и 3, -2, -7.