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.