Дан набор из N целых чисел a₁, a₂, …, a_N. Разбейте его на две прогрессии: арифметическую и геометрическую. Каждое число должно войти ровно в одну из прогрессий, и в каждую из прогрессий должно попасть хотя бы одно число.

Напоминаем, что арифметическая прогрессия — это последовательность чисел вида b, b + d, b + 2d, …, b + (k − 1) · d, где b — первый элемент прогрессии, d — шаг прогрессии, k — её длина. А геометрическая прогрессия — это последовательность чисел вида c, c · q, c · q², …, c · q^{t − 1}, где c — первый элемент прогрессии, q — знаменатель прогрессии (q ≠ 0), t — её длина.

В первой строке дано целое число N — количество чисел в наборе (2 ≤ N ≤ 50 000).

Во второй строке через пробел даны N целых чисел a₁, a₂, …, a_N — сам набор чисел (0 ≤ a_i ≤ 1 000 000 000).

Если решения не существует, в единственной строке выведите «−1» (без кавычек).

Иначе, в первой строке выведите целое число — длину арифметической прогрессии. Во второй строке выведите через пробел числа из арифметической прогрессии в том порядке, в котором они идут в этой прогрессии. В третьей строке выведите через пробел числа из геометрической прогрессии в том порядке, в котором они идут в этой прогрессии.

В первом примере найдена арифметическая прогрессия с шагом 3 и геометрическая прогрессия со знаменателем 2. Правильным ответом также является пара из арифметической прогрессии 0, 2, 4, 6 и геометрической прогрессии 3, 8, а также арифметическая прогрессия 0, 2, 4, 6, 8 и геометрическая прогрессия 3.

Во втором примере геометрическая прогрессия имеет знаменатель 1.5. Обратите внимание, что геометрическая прогрессия может иметь нецелый знаменатель и при этом состоять из целых чисел.

В третьем примере геометрическая прогрессия имеет первый элемент 0, а знаменателем может быть любое положительное число.