Владимир Геннадьевич готовит задание по высшей математике для студентов.
Задание планируется такое. Дано $$$n$$$ целых чисел $$$x_1, x_2, \ldots, x_n$$$ и натуральное число $$$m$$$, $$$1 \le m \lt 2^n$$$.
Требуется выбрать $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$, каждое из которых равно $$$0$$$, $$$-1$$$ или $$$1$$$, при этом хотя бы одно из них должно быть отлично от $$$0$$$, а сумма $$$a_1x_1 + a_2x_2 + \ldots + a_nx_n$$$ должна делиться на $$$m$$$ без остатка.
Владимир Геннадьевич придумал ответ на задание, которое он хочет дать студентам: он выбрал $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$-1 \leq a_i \leq 1$$$), хотя бы одно из них не равно $$$0$$$. Чтобы выполненные задания было легче проверить, он хочет придумать такие числа $$$x_1, x_2, \ldots, x_n$$$ и натуральное число $$$m$$$, чтобы выбранные им числа $$$a_1, a_2, \ldots, a_n$$$ были единственным подходящим решением. К сожалению, это невозможно, так как числа $$$-a_1, -a_2, \ldots, -a_n$$$ также подходят.
Тогда Владимир Геннадьевич ослабил свои требования: он хочет, чтобы других решений, кроме $$$a_1, a_2, \ldots, a_n$$$ и $$$-a_1, -a_2, \ldots, -a_n$$$ не существовало.
Помогите ему выбрать числа $$$x_1, x_2, \ldots, x_n$$$ и $$$m$$$ для задания.
В первой строке находится число $$$n$$$ ($$$1 \leq n \leq 30$$$).
В следующей строке дано $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$-1 \leq a_i \leq 1$$$). Гарантируется, что хотя бы одно из чисел $$$a_i$$$ не равно $$$0$$$.
В первой строке выведите натуральное число $$$m$$$ ($$$1 \leq m \lt 2^n$$$).
В следующей строке выведите $$$n$$$ целых чисел $$$x_1, x_2, \ldots, x_n$$$ ($$$-2^{30} \lt x_i \lt 2^{30}$$$).
Если подходящих вариантов несколько, выведите любой из них.
Гарантируется, что решение всегда существует.
2 1 -1
3 1 4
В примере студенты должны выбрать числа $$$a_1$$$ и $$$a_2$$$, чтобы число $$$a_1 + 4a_2$$$ делилось на $$$3$$$. Подходят два решения:
