Внутрішній продукт

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

Це інтерактивна задача.

Зеник і Марічка втомились від важкої директорської роботи в компанії PLVIV та хочуть відпочити. Під час відпочинку вони гратимуть у гру.

Ось правила гри.

На столі лежать \(n\) карт. На кожній карті записано ціле число \(a_i\).

Гравці роблять ходи по черзі, починаючи з Марічки. За хід гравець вибирає одну карту зі столу та забирає її собі.

Гра завершується, коли гравці забрали всі карти зі столу. Після завершення гри обчислюється сума чисел на картах кожного гравця. Якщо ці суми однакові, виграє Зеник, якщо ж різні — виграє Марічка.

Кожен з гравців хоче втерти носа своєму супернику. Для цього директорам потрібен симулятор цієї гри, щоб вони могли тренуватися.

Симулятор повинен працювати в режимі «людина проти комп’ютера». Причому симулятор сам вибиратиме, за кого він гратиме — за Зеника чи за Марічку. Симулятор повинен завжди вигравати в суперника, незалежно від того, які ходи робить суперник.

Напишіть для Зеника з Марічкою програму-симулятор гри.

У першу чергу програма повинна вибрати, за кого вона гратиме. Потім програма повинна просимулювати гру і грати проти суперника.

Вхідні дані

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

У другому рядку записано \(n\) цілих чисел \(a_i\), що записані на картах.

Після зчитування цих чисел ваша програма повинна вивести, за кого вона гратиме — Marichka або Zenyk.

Тепер гравці починають робити ходи по черзі, починаючи з Марічки.

Щоб зробити хід, ваша програма повинна вивести число на карті, яку ви хочете забрати собі.

Кожен хід суперника (число на карті, яке він забирає) буде даватися вашій програмі на вхід і ваша програма повинна зчитати його.

Якщо ваш хід невалідний (наприклад, на столі нема карт з таким числом), замість ходу суперника вашій програмі буде задано на вхід число -1 та гра припиниться. У такому випадку завершiть роботу програми, щоб отримати вердикт Неправильна вiдповiдь. Якщо цього не зробити, ви можете отримати вердикт Помилка часу виконання.

Подбайте про виклик методу flush після виводу кожного рядка. Для цього можна використовувати:

• fflush(stdout), cout << endl або cout.flush() в C++;

• System.out.flush() в Java;

• flush(output) в Pascal;

• sys.stdout.flush() в Python;

• Console.Out.Flush() в C#.

Обмеження

\(2 \le n \le 10^3\),

\(1 \le a_i \le 10^3\).

Примітки

Розгляньмо приклад для \(n=7\), \(a = (1, 2, 3, 4, 5, 6, 7)\), де програма грає за Марічку.

У програми (Марічки) є карти \(4, 2, 6, 5\), а в суперника (Зеника) — карти \(1, 3, 7\). Сума чисел на картах Марічки дорівнює \(4+2+6+5=17\), а на картах Зеника — \(1+3+7=11\). Ці суми різні, тому виграє програма, яка грала за Марічку.

Нижче наведено інший приклад для \(n=4\), \(a = (74, 74, 74, 74)\), де програма цього разу грає за Зеника.

У гравців однаковий набір карт на руках, отже суми чисел на картах також однакові. Переможцем гри є програма, яка грала за Зеника.