406400: GYM102396 E 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.

2
1 -1

3
1 4

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$$$).