题目背景

小 S 共有 $n$ 只可爱的喵喵，第 $i$ 只喵喵有可爱度 $a_i$。小 S 想要把他的喵喵分成两组。考虑到小 S 的喵喵不像某些喵喵有九条命，他的喵喵只有一条，于是一只喵喵不能被同时分到两组内（请不要试图想象这个画面）。同时，如果一只喵喵没有被分到任意一组，他就会十分生气，很有可能导致小 S 失眠。

当然，小 S 也希望两组的组可爱度相等。即存在一个正整数 $x$，使得其中一组的 $\gcd(x, a_i)$ 之和等于另一组的 $\gcd(x, a_i)$ 之和。请你判断是否可以使得小 S 可以将喵喵分成两组，并可以找出一个 $x$ 使得两组的组可爱度相等。

题目描述

给定正整数 $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$ 的解。

输入格式

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

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

输出格式

如无解，仅输出一行一个整数 $-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

提示

本题采用捆绑测试。

• 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$。