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

Limits: 2 sec., 256 MiB

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

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

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

Input

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

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

Output

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

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

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

Constraints

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

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

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

$2 \le n \le 4$.

Samples

Input (stdin) сopy	Output (stdout) сopy
5 1 1 1 1 1	Marichka 1 1 0 0 0

Input (stdin) сopy	Output (stdout) сopy
2 1 1	Zenyk

Notes

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