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

Обмеження: 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

Примітки

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