A. Non-trivial Energy of Crystals
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Hamster Shustrik and Hedgehog Shurshik are conducting a risky experiment.

They have $$$n$$$ magical crystals, each with an integer energy level. The crystals must be placed into two chambers for further observation. In order for the experiment not to fail, the following rule must be satisfied: two crystals whose energies sum to a prime number must not be placed in the same chamber.

Help the hamster and the hedgehog find such a distribution of the crystals into two chambers that no pair of crystals violates the rule described above.

Shustrik and Shurshik remind that a prime number is a natural (positive integer) number that has exactly two distinct natural divisors — one and itself.

Input

The first line of input contains an integer $$$n$$$—the number of magical crystals ($$$1 \le n \le 10^5$$$).

The second line of input contains $$$n$$$ integers $$$a_i$$$—the energies of all magical crystals ($$$2 \le a_i \le 10^{12}$$$).

Output

If it is impossible to distribute the crystals into two chambers while adhering to the described rule, output $$$-1 -1$$$ (two minus one numbers separated by a space) in a single line. If it is possible to distribute the crystals, then:

In the first line, output the numbers $$$n_1$$$ and $$$n_2$$$—the number of crystals in the first and second chambers, respectively.

In the second line, output the energies of the magical crystals from the first chamber in any order, separating the elements with spaces.

In the third line, output the energies of the magical crystals from the second chamber in any order, also separating the elements with spaces.

If there are multiple distributions, output any of them.

Scoring

The tests for this problem consist of seven groups. Points for each group are awarded only if all tests of the group, all tests of the necessary groups, and tests from the problem statement are passed.

GroupPointsAdditional Constraints
120$$$n \le 10, a_i \le 100$$$–
215$$$n \le 200, a_i \le 200$$$1
320$$$n \le 200, a_i \le 3 \cdot 10^6$$$1, 2
415$$$n \le 3\,000, a_i \le 3 \cdot 10^6$$$1, 2, 3
55$$$n \le 10\,000, a_i \le 5 \cdot 10^7$$$1–4
610$$$a_i \le 10^9$$$1–5
715–1–6
Examples
Input
2
2 3
Output
1 1
2 
3
Input
6
7 14 30 91 15 74
Output
3 3
7 14 74
30 91 15
Note

In the first example, the magical crystals with energies $$$2$$$ and $$$3$$$ cannot be in the same chamber, as $$$2 + 3 = 5$$$, and the number $$$5$$$ is a prime number.

In the second example, multiple distributions may be suitable as answers, including the distribution into $$$(30, 15)$$$ and $$$(7, 14, 91, 74)$$$ and the distribution into $$$(30, 14, 74)$$$ and $$$(7, 91, 15)$$$.