Background

Xiao S has a total of $n$ cute cats. The $i$-th cat has cuteness $a_i$. Xiao S wants to split his cats into two groups. Considering that Xiao S's cats are not like some cats that have nine lives, each of his cats has only one life, so a cat cannot be put into both groups at the same time (please do not try to imagine this scene). Also, if a cat is not assigned to any group, it will be very angry, and it may very likely cause Xiao S to suffer from insomnia.

Of course, Xiao S also hopes that the two groups have the same group cuteness. That is, there exists a positive integer $x$ such that the sum of $\gcd(x, a_i)$ in one group equals the sum of $\gcd(x, a_i)$ in the other group. Please determine whether Xiao S can split the cats into two groups, and whether you can find an $x$ that makes the group cuteness of the two groups equal.

Problem Description

Given a positive integer $n$ and a sequence $a$ of $n$ positive integers, please partition $a$ into two sets $B, C$ and give a positive integer $x$ such that $\sum_{y\in B}\gcd(x,y) = \sum_{y\in C}\gcd(x,y)$. If there is no solution, output $-1$.

You need to guarantee $1 \leq x \leq 10^9$. It is guaranteed that under this problem's Constraints, if a solution exists then there is always a solution with $x \leq 10^9$.

Input Format

The first line contains one positive integer $n$.

The next line contains $n$ positive integers, where the $i$-th one denotes $a_i$.

Output Format

If there is no solution, output a single line with the integer $-1$. Otherwise:

The first line outputs one positive integer $x$.

The second line outputs a $\tt 01$ string of length $n$. The $i$-th character is $\tt 0$ meaning that $a_i$ is placed into set $B$, and $\tt 1$ meaning that $a_i$ is placed into set $C$.

3
1 1 1

-1

4
4 1 2 3

3
0001

Hint

This problem uses bundled testdata.

• Subtask 0 (2 pts): $n$ is even.
• Subtask 1 (8 pts): all $a_i$ are odd.
• Subtask 2 (15 pts): $n \leq 50$, $a_i \leq 50$.
• Subtask 3 (25 pts): $n \leq 10^3$, $a_i \leq 10^3$.
• Subtask 4 (50 pts): no special restrictions.

For all testdata, $1 \leq n \leq 10^5$, $1 \leq a_i \leq 10^6$.

Translated by ChatGPT 5