ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

## 2158. Two progressions

Time limit: 2.0 second
Memory limit: 256 MB
Given a set of N integers a1, a2, …, aN. 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 · q2, …, c · qt − 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 a1, a2, …, aN — the set of numbers (0 ≤ ai ≤ 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.

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