Unique Solution

The professor is preparing a task for higher math students. 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$, with at least one non-zero value. 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 is a given array of integers $a_1, a_2, \ldots, a_n$ ($-1 \le a_i \le 1$, at least one of them is not $0$). To make checking students' solutions easier, he wants to choose integers $x_1, \ldots, x_n$ and an integer $m$ so that his array is the only possible solution. This is impossible, because the array $-a_1, \ldots, -a_n$ is always a solution too.

So the professor relaxes his requirements and wants the only two solutions to be $a_1, \ldots, a_n$ and $-a_1, \ldots, -a_n$. Help him choose integers $x_1, \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 an 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_2 = -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$). The professor's requirements are met.