19722번 - Unique Solution 스페셜 저지다국어

문제

Professor is preparing a task for higher math students.

The task is the following. The students are given $n$ integers $x_1, x_2, \ldots, x_n,ドル and an integer $m$ (1ドル \le m < 2^n$).

The student must choose $n$ integers $a_1, a_2, \ldots, a_n,ドル each either $-1,ドル 0ドル,ドル or 1ドル,ドル at least one non-zero value be chosen. The chosen integers must satisfy the condition that $a_1x_1+a_2x_2+\ldots+a_nx_n$ is divisible by $m$.

The professor has decided that the answer to the task should be some given array of integers $a_1, a_2, \ldots, a_n$ ($-1 \le a_i \le 1,ドル at least one of them is not equal to 0ドル$). To make his job of checking students' solutions easier, he wants to choose such integers $x_1, x_2, \ldots, x_n$ and an integer $m,ドル that his array $a_1, a_2, \ldots, a_n$ is the only possible solution. Unfortunately it is not possible, because the array $-a_1, -a_2, \ldots, -a_n$ is always a solution too.

So the professor relaxes his requirements, and wants the only two solutions be $a_1, a_2, \ldots, a_n$ and $-a_1, -a_2, \ldots, -a_n$.

Help him choose integers $x_1, x_2, \ldots, x_n$ and an integer $m$.

입력

The first line of input contains an integer $n$ (1ドル \leq n \leq 30$).

The next line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-1 \leq a_i \leq 1$). At least one of $a_i$ is not equal to 0ドル$.

출력

The first line of output must contain and integer $m$ (1ドル \le m < 2^n$).

The next line must contain $n$ integers $x_1, x_2, \ldots, x_n$ ($-2^{30} < x_i < 2^{30}$).

If there are several possible answers, output any of them.

It is known that the answer always exists.

제한

힌트

In the given example the students must choose $a_1$ and $a_2$ so that $a_1 + 4a_2$ is divisible by 3ドル$. There are two possible solutions:

• $a_1 = 1,ドル $a_1 = -1$ ($a_1 + 4a_2 = 1 - 4 = -3,ドル divisible by 3ドル$) and
• $a_1 = -1,ドル $a_2 = 1$ ($a_1 + 4a_2 = -1 + 4 = 3,ドル divisible by 3ドル$).

Professor's requirements are met.