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

---

استاد در حال آماده کردن یک مسئله برای دانشجویان است. مسئله به این صورت است که به دانشجویان \(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\) بخش‌پذیر است).

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