Нерівноправна гра

Обмеження: 2 сек., 256 МіБ

Зеник та Марічка вирішили зіграти в ігри для того, щоб відпочити від інтенсивної підготовки до ЗНО. Зеник запропонував зіграти у гру з камінцями. У цій грі гравцям дають $n$ купок камінців, пронумерованих від 1 до $n$. У купці з номером $i$ є $a_i$ камінців. Гравці ходять по черзі, починаючи з Марічки. За один хід гравець може обрати довільну купку з додатною кількістю камінців і забрати з неї додатну кількість камінців. Програє той гравець, який не може зробити ходу.

Марічка не хоче грати в цю гру, оскільки вважає її дуже нудною, отож вона запропонувала модифікувати її. Тепер Марічка має право забирати додатну кількість камінців з будь-якої підмножини купок розміру від 1 до $n$-1. Правила гри для Зеника залишаються незмінними.

Самовпевнений Зеник погодився на таку модифікацію, не підозрюючи того, що Марічка має величезну перевагу в такій грі. Хто виграє при оптимальній грі обох гравців?

Вхідні дані

У першому рядку задано одне ціле число $n$ — кількість купок.

У другому рядку задано $n$ цілих чисел — $a_1$, $a_2$, ..., $a_n$.

Вихідні дані

У першому рядку, у разі перемоги Марічки, виведіть Marichka, інакше виведіть Zenyk.

Якщо Марічка здобуде перемогу, то у наступному рядку виведіть $n$ цілих невід’ємних чисел $b_i, 0 \le b_i \le a_i$, розділених пропусками, де $b_i$ означає кількість камінців, яку Марічка повинна забрати з купки з номером $i$ першим ходом.

Кількість нулів у вихідному рядку не може бути рівна 0 або $n$.

Обмеження

$2 \le n \le 10^5$,

$1 \le a_i \le 10^9$,

для 40% тестів виконується:

$2 \le n \le 4$.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
5 1 1 1 1 1	Marichka 1 1 0 0 0

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
2 1 1	Zenyk

Примітки

У першому прикладі Марічка може забрати першим ходом камінці з першої та другої купки. Незалежно від рішення Зеника, на наступному ході залишаться дві непорожні купки, з яких Марічка зможе забрати усі камінці.