Children's duet

Limits: 1 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Arseniy and Yulia have a chance to win a whole bag of candies from their math teacher if they can complete his task. Teacher has a set of cards with different numbers. First, Arseniy takes some of these numbers for himself, and then Yulia takes some of the remaining ones. Everyone must take at least one card. Then Arseniy and Yulia calculate the sum of the numbers on their cards and if these sums have at least one common divisor greater than one, they get the candies. The teacher is kind, so a way to get candies will always exist — help the children figure out how. If there are several ways to achieve the goal, you can choose any of them.

Input

The first line contains a single number \(n\) — the number of cards. The second line contains \(n\) space-separated numbers — the numbers on the cards.

Output

In the first line, output two space-separated numbers \(k, l\) — the number of cards that Arsen and Yulia must take, respectively. In the second line, output \(k\) numbers — the cards chosen by Arsen. In the third line, output \(l\) numbers — the cards chosen by Yulia.

Constraints

\(4 \leq n \leq 1000\),

Each of the numbers on the cards is from \(1\) to \(10^6\).

Samples

Input (stdin) сopy	Output (stdout) сopy
7 19 7 11 31 99 13 17	3 3 7 11 17 31 13 19

Input (stdin) сopy	Output (stdout) сopy
4 4 7 17 17	1 1 17 17

Notes

In the first test, we get sums 35 and 63 — both are divisible by 7. In the second test, there are two identical numbers greater than one, so they are both divisible by themselves.