Given a set of N integers a_{1}, a_{2}, …, 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^{2}, …, 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.
Input
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_{1}, a_{2}, …, a_{N} — the set of numbers (0 ≤ a_{i} ≤ 1 000 000 000).
Output
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.
Samples
input  output 

6
0 2 3 4 6 8
 3
0 3 6
2 4 8

6
4 4 6 6 8 9
 3
4 6 8
4 6 9

4
0 0 0 0
 1
0
0 0 0

5
0 0 1 1 2
 1

Notes
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 noninteger 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.
Problem Author: Valentin Zuev
Problem Source: Ural School Programming Contest 2021