• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

استاد در حال آماده کردن یک مسئله برای دانشجویان است. مسئله به این صورت است که به دانشجویان $n$ عدد صحیح $x_1, x_2, \ldots, x_n$ و یک عدد صحیح $m$ که $1 \le m \lt 2^n$ است، داده می‌شود.

دانشجو باید $n$ عدد صحیح $a_1, a_2, \ldots, a_n$ را انتخاب کند، به طوری که هر یک از آن‌ها برابر با $-1$، $0$ یا $1$ باشند و حداقل یکی از این اعداد غیر صفر باشد. اعداد انتخاب‌شده باید این شرط را برآورده کنند که $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, 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 \le 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$ بخش‌پذیر باشد. دو پاسخ ممکن وجود دارد:

• $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$، که بر $3$ بخش‌پذیر است).

شرایط استاد برآورده شده است.