유일한 해

교수님이 고급 수학 과제를 학생들에게 낼 준비를 하고 있다. 학생들에게 정수 $n$개 $x_1, x_2, \ldots, x_n$과 정수 $m$ ($1 \le m < 2^n$)이 주어진다. 학생은 각 값이 $-1$, $0$, $1$ 중 하나인 정수 $a_1, a_2, \ldots, a_n$을 $n$개 고르되, 적어도 하나는 0이 아니어야 한다. 고른 정수는 $a_1x_1+a_2x_2+\ldots+a_nx_n$이 $m$으로 나누어떨어져야 한다.

교수님은 정답을 주어진 정수 배열 $a_1, a_2, \ldots, a_n$ ($-1 \le a_i \le 1$, 적어도 하나는 0이 아님)으로 정했다. 학생들의 풀이를 쉽게 확인하려고 이 배열만 가능한 풀이가 되도록 정수 $x_1, \ldots, x_n$과 $m$을 고르고 싶어 한다. 그런데 배열 $-a_1, \ldots, -a_n$도 항상 풀이이므로 이는 불가능하다.

그래서 교수님은 조건을 완화해, 풀이가 $a_1, \ldots, a_n$과 $-a_1, \ldots, -a_n$ 두 개뿐이기를 바란다. 정수 $x_1, \ldots, x_n$과 $m$을 골라 주자.

첫 줄에 정수 $n$ ($1 \leq n \leq 30$)이 주어진다. 다음 줄에는 정수 $a_1, a_2, \ldots, a_n$ ($-1 \leq a_i \leq 1$)이 주어진다. 적어도 하나의 $a_i$는 0이 아니다.

첫 줄에 정수 $m$ ($1 \le m < 2^n$)을 출력한다. 다음 줄에는 정수 $x_1, x_2, \ldots, x_n$ ($-2^{30} < x_i < 2^{30}$)을 출력한다. 가능한 답이 여러 개이면 그중 아무것이나 출력해도 된다. 답은 항상 존재하는 것으로 알려져 있다.

예제에서 학생들은 $a_1 + 4a_2$가 3으로 나누어떨어지도록 $a_1$과 $a_2$를 골라야 한다. 가능한 풀이는 두 가지다. $a_1 = 1$, $a_2 = -1$이면 $a_1 + 4a_2 = 1 - 4 = -3$으로 3으로 나누어떨어지고, $a_1 = -1$, $a_2 = 1$이면 $a_1 + 4a_2 = -1 + 4 = 3$으로 역시 나누어떨어진다. 교수님의 요구 조건이 충족된다.