CF1725H.Hot Black Hot White

One day, you are accepted as being Dr. Chanek's assistant. The first task given by Dr. Chanek to you is to take care and store his magical stones.

Dr. Chanek has $N$ magical stones with $N$ being an even number. Those magical stones are numbered from $1$ to $N$. Magical stone $i$ has a strength of $A_i$. A magical stone can be painted with two colours, namely the colour black or the colour white. You are tasked to paint the magical stones with the colour black or white and store the magical stones into a magic box with a magic coefficient $Z$ ($0 \leq Z \leq 2$). The painting of the magical stones must be done in a way such that there are $\frac{N}{2}$ black magical stones and $\frac{N}{2}$ white magical stones.

Define $\text{concat}(x, y)$ for two integers $x$ and $y$ as the result of concatenating the digits of $x$ to the left of $y$ in their decimal representation without changing the order. As an example, $\text{concat}(10, 24)$ will result in $1024$.

For a magic box with a magic coefficient $Z$, magical stone $i$ will react with magical stone $j$ if the colours of both stones are different and $\text{concat}(A_i, A_j) \times \text{concat}(A_j, A_i) + A_i \times A_j \equiv Z \mod 3$. A magical stone that is reacting will be very hot and dangerous. Because of that, you must colour the magical stones and determine the magic coefficient $Z$ of the magic box in a way such that there is no magical stone that reacts, or report if it is impossible.

有一天，你被接纳为陈博士（Dr. Chanek）的助手。陈博士交给你的第一项任务是照看并储存他的魔法石。

陈博士有 $N$ 颗魔法石，其中 $N$ 为偶数。这些魔法石编号为 $1$ 到 $N$。第 $i$ 颗魔法石的强度为 $A_i$。每颗魔法石可被涂成两种颜色之一：黑色或白色。你的任务是将这些魔法石涂成黑色或白色，并将其存入一个具有魔法系数 $Z$（$0 \leq Z \leq 2$）的魔法盒中。涂色必须满足：恰好有 $\frac{N}{2}$ 颗魔法石为黑色，且恰好有 $\frac{N}{2}$ 颗魔法石为白色。

对两个整数 $x$ 和 $y$，定义 $\text{concat}(x, y)$ 为：将 $x$ 的十进制表示的各位数字按原顺序拼接在 $y$ 的十进制表示的左侧所得的整数。例如，$\text{concat}(10, 24)$ 的结果为 $1024$。

对于一个魔法系数为 $Z$ 的魔法盒，若魔法石 $i$ 与魔法石 $j$ 颜色不同，且满足

$$\text{concat}(A_i, A_j) \times \text{concat}(A_j, A_i) + A_i \times A_j \equiv Z \pmod{3},$$

则魔法石 $i$ 与魔法石 $j$ 将发生反应。发生反应的魔法石会变得极其炽热且危险。因此，你必须对魔法石进行涂色，并确定魔法盒的魔法系数 $Z$，使得没有任何一对魔法石发生反应；若不可能实现，则需报告该情况。

The first line contains a single even integer $N$ ($2 \le N \le 10^5$) — the number of magical stones Dr. Chanek has.

The second line contains $N$ integer $A_1, A_2, \ldots, A_N$ ($1 \leq A_i \leq 10^9$) — the strengths of all magical stones.

第一行包含一个偶数整数 $N$（$2 \le N \le 10^5$）—— 表示陈博士拥有的魔法石数量。

第二行包含 $N$ 个整数 $A_1, A_2, \ldots, A_N$（$1 \leq A_i \leq 10^9$）—— 表示所有魔法石的强度。

If it is not possible to satisfy the condition of the problem, output $-1$.

Otherwise, output two lines. The first line contains an integer $Z$ denoting the magic coefficient of the magic box. The second line contains a string $S$ of length $N$. $S_i$ is $0$ if magical stone $i$ is coloured black or $1$ if magical stone $i$ is coloured white. If there are more than one possibilities of colouring and choosing the magic coefficient $Z$, output any of them.

如果无法满足题目的条件，则输出 $-1$。

否则，输出两行。第一行包含一个整数 $Z$，表示魔法盒的魔法系数。第二行包含一个长度为 $N$ 的字符串 $S$；其中 $S_i$ 为 $0$ 表示第 $i$ 颗魔法石被染成黑色，为 $1$ 表示第 $i$ 颗魔法石被染成白色。若存在多种染色方案及对应的魔法系数 $Z$，输出任意一种即可。

By giving the above colouring, it can be seen that:

• $i=1, j=2 \longrightarrow \text{concat}(4, 10) \times \text{concat}(10, 4) + 10 \times 4 = 410 \times 104 + 40 = 42680 \equiv 2 \mod 3$
• $i=1, j=3 \longrightarrow \text{concat}(4, 9) \times \text{concat}(9, 4) + 4 \times 9 = 49 \times 94 + 36 = 4642 \equiv 1 \mod 3$
• $i=4, j=2 \longrightarrow \text{concat}(14, 10) \times \text{concat}(10, 14) + 10 \times 14 = 1410 \times 1014 + 140 = 1429880 \equiv 2 \mod 3$
• $i=4, j=3 \longrightarrow \text{concat}(14, 9) \times \text{concat}(9, 14) + 14 \times 9 = 149 \times 914 + 126 = 136312 \equiv 1 \mod 3$

Because of that, by choosing $Z = 0$, it can be guaranteed that there is no magical stone that reacts.

通过上述染色方案可以发现：

• $i=1, j=2 \longrightarrow \text{concat}(4, 10) \times \text{concat}(10, 4) + 10 \times 4 = 410 \times 104 + 40 = 42680 \equiv 2 \mod 3$
• $i=1, j=3 \longrightarrow \text{concat}(4, 9) \times \text{concat}(9, 4) + 4 \times 9 = 49 \times 94 + 36 = 4642 \equiv 1 \mod 3$
• $i=4, j=2 \longrightarrow \text{concat}(14, 10) \times \text{concat}(10, 14) + 10 \times 14 = 1410 \times 1014 + 140 = 1429880 \equiv 2 \mod 3$
• $i=4, j=3 \longrightarrow \text{concat}(14, 9) \times \text{concat}(9, 14) + 14 \times 9 = 149 \times 914 + 126 = 136312 \equiv 1 \mod 3$

因此，选择 $Z = 0$ 即可保证不存在发生反应的魔法石。