Given a set of N integers a₁, a₂, …, a_N. Divide it into two progressions: arithmetic and geometric. Each number must be included in exactly one of the progressions, and each progression must contain at least one number.

Reminder: an arithmetic progression is a sequence of numbers of the form b, b + d, b + 2d, …, b + (k − 1) · d, where b is the first element of the progression, d is the progression step, and k is its length. A geometric progression is a sequence of numbers of the form c, c · q, c · q², …, c · q^{t − 1}, where c is the first element of the progression, q is the common ratio (q ≠ 0), and t is its length.

The first line contains an integer N — the number of numbers in the set (2 ≤ N ≤ 50 000).

The second line contains N integers a₁, a₂, …, a_N — the set of numbers (0 ≤ a_i ≤ 1 000 000 000).

If there is no solution, output «−1» (without quotes) on a single line.

Otherwise, on the first line, output an integer — the length of the arithmetic progression. On the second line, output the numbers from the arithmetic progression separated by spaces in the order they appear in the progression. On the third line, output the numbers from the geometric progression separated by spaces in the order they appear in the progression.

In the first example, an arithmetic progression with a step of 3 and a geometric progression with a common ratio of 2 are found. The correct answer is also a pair of an arithmetic progression 0, 2, 4, 6 and a geometric progression 3, 8, as well as an arithmetic progression 0, 2, 4, 6, 8 and a geometric progression 3.

In the second example, the geometric progression has a common ratio of 1.5. Note that a geometric progression can have a non-integer common ratio and still consist of integers.

In the third example, the geometric progression has the first element 0, and the common ratio can be any positive number.