Description

给定正整数 $n$ 及长度为 $n$ 的正整数序列 $a$，请你将 $a$ 划分为两个集合 $B, C$ 并给出正整数 $x$，使得 $\sum_{y\in B}\gcd(x,y) = \sum_{y\in C}\gcd(x,y)$。如果无解，输出 $-1$。

你需要保证 $1 \leq x \leq 10^9$，保证在本题的数据约束下若有解则总有 $x \leq 10^9$ 的解。

Input Format

第一行一个正整数 $n$。

接下来一行为 $n$ 个正整数，其中第 $i$ 个表示 $a_i$。

Output Format

如无解，仅输出一行一个整数 $-1$。否则：

第一行输出一个正整数 $x$。

第二行输出一个长度为 $n$ 的 $\tt 01$ 串，第 $i$ 个数为 $\tt 0$ 代表 $a_i$ 被划分到集合 $B$ 中，为 $\tt 1$ 代表 $a_i$ 被划分到集合 $C$ 中。

3
1 1 1

-1

4
4 1 2 3

3
0001

Hint

本题采用捆绑测试。

• Subtask 0（2 pts）：$n$ 为偶数。
• Subtask 1（8 pts）：$a_i$ 均为奇数。
• 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）：无特殊限制。

对于所有数据，$1 \leq n \leq 10^5$，$1 \leq a_i \leq 10^6$。