Це інтерактивна задача. Прочитайте умовну повністю, щоб зрозуміти, як працювати з такими задачами.

Є ~N~ купок, кожна з яких містить деяку кількість паличок. Двоє грають у таку гру. Кожен з гравців на кожному своєму ході може забрати з будь-якої однієї купки будь-яку кількість паличок, від 1 до зразу всіх паличок цієї купки. Палички можна лише забирати (ні додавати, ні перекладувати з купки в купку не можна). Ніяких інших варіантів ходу нема. Коли купка стає порожньою (кількість паличок=0), гра просто продовжується для решти купок. Ходять гравці по черзі, пропускати хід не можна. Виграє той, хто забирає останню паличку (можливо, разом із ще деякими) з останньої купки. (Інакше кажучи, виграє той, після чийого ходу не лишається жодної палички в жодній купці.)

Напишіть програму, яка інтерактивно гратиме за першого гравця.

Ця задача є інтерактивною: Ваша програма не отримає всіх вхідних даних на початку, а отримуватиме по мірі виконання доуточнення, що залежатимуть від попередніх дій Вашої програми. Тим не менш, її перевірка буде автоматичною. Тому, слід чітко дотримуватися формату спілкування з програмою, яка грає роль суперника.

Протокол взаємодії

На початку, один раз, Ваша програма повинна прочитати початкову позицію гри.

Перший рядок містить єдине ціле число ~N~ (~1\leqslant N\leqslant 12~) — кількість купок. Другий рядок містить рівно ~N~ чисел ~k_1~, ~k_2~, ..., ~k_N~, розділених одинарними пропусками (пробілами) — початкові кількості паличок у кожній з купок. Всі числа ~k_1~, ~k_2~, ..., ~k_N~ є цілими, у межах від 1 до 1234, серед них можуть бути як однакові, так і різні.

Потім Ваша програма повинна повторювати такий цикл:

1. Вивести два числа, розділені пропуском, у окремому рядку – свій хід, тобто номер купки, з якої вона забирає палички, та кількість паличок, які вона забирає. Це повинно бути ціле число від 1 до поточної кількості паличок у відповідній купці (обидві межі включно). Купки занумеровані з одиниці: 1, 2, ..., ~N~. Якщо внаслідок попередніх ходів деякі купки вже стали порожніми, всі купки зберігають свої початкові номери.
2. Якщо це була остання купка й вона після цього стає порожньою, вивести окремим рядком фразу «I won!» (без лапок, символ-у-символ згідно зразку) й завершити роботу.
3. Інакше, прочитати хід програми-суперниці, в такому ж форматі: номер купки, з якої вона забирає палички, одинарний пропуск (пробіл), кількість паличок, які вона забирає. Гарантовано, що хід допустимий: купка з таким номером (нумерація з одиниці) існує й містить хоча б одну паличку, а кількість паличок є цілим числом від 1 до поточного залишку паличок у купці (обидві межі включно). Само собою, ця гарантія дійсна лише за умови, що Ваша програма правильно визначила, що гра ще не закінчилася.
4. Якщо це була остання купка й вона після цього стає порожньою, вивести окремим рядком фразу «You won...» (без лапок, символ-у-символ згідно зразку) й завершити роботу.

Все вищезгадане повинно повторюватися, доки не будуть забрані всі палички з усіх купок (тобто, доки якась із програм-гравців не виграє). Програма-суперниця не виводить фраз «I won!» / «You won...» чи якихось їх аналогів.

Наполегливо рекомендується, щоб Ваша програма після кожного свого виведення робила дію flush(output) (Pascal), вона ж cout.flush() (C++), вона ж fflush(stdout) (C), вона ж sys.stdout.flush() (Python), вона ж System.out.flush() (Java). Це істотно зменшує ризик, що проміжна відповідь «загубиться» десь по дорозі, не дійшовши до програми-суперниці.

Приклад взаємодії

Примітки

Нібито порожні рядки між різними ходами у прикладі зроблені суто для того, щоб краще було видно, хто коли ходить; вводити/виводити їх не треба.

Загальний хід гри з прикладу можна прокоментувати так. Є дві купки, в одній 3 палички, в іншій 4. Позначимо як (3,4). Ваша програма забирає 1 паличку з купки №2, лишається (3,3); програма-суперниця забирає 2 палички з купки №2, лишається (3,1); Ваша програма забирає 2 палички з купки №1, лишається (1,1); програма-суперниця забирає останню 1 паличку з купки №1, лишається (0,1); Ваша програма забирає останню 1 паличку з останньої купки №2, повідомляє про свій виграш і завершує роботу.

Оцінювання

Оцінювання поблокове, тобто для нарахування балів за блок потрібно, щоб пройшли усі тести цього блоку. Тест з умови при перевірці не використовується. У п'яти блоках тестів (усіх, крім останнього) Ваша програма матиме справу з ідеальною програмою-суперницею, яка не робить помилок.

10% балів припадає на блок № 1, де ~N=1~ (отже, в усіх тестах цього блоку можна і треба виграти).

Ще 15% балів припадає на блок № 2, де ~N=2~.

Ще 15% балів припадає на блок № 3, де ~N=3~.

Ще 15% балів припадає на блок № 4, де ~1\leqslant N\leqslant 12~.

У кожному з блоків №№2-4 є як тести, де Ваша програма може і повинна вигравати, так і тести, де Ваша програма не має шансів виграти і повинна просто достойно згідно правил гри програти.

Ще 10% балів припадає на блок № 5, де ~1\leqslant N\leqslant 12~, причому в жодному з тестів цього блоку виграти не можна, потрібно лише достойно згідно правил гри програвати.

Решта 35% балів припадає на останній блок № 6, де Вашій програмі слід мати справу з різними програмами-суперницями, які грати не вміють — роблять ходи, які дотримуються формальних правил гри, але можуть вибирати не найкращий з допустимих ходів, дотримуючись кожна своїх власних уявлень про те, як варто грати в цю гру. Для проходження цього блоку Ваша програма має в кожному з тестів виграти, скориставшися (згідно правил гри) помилками чи іншими неадекватностями програми-суперниці. В цьому блоці № 6 всі тести відносно великі (~7\leqslant N\leqslant 12~, всі значення ~k_i~ від 98 до 1234).

За будь-яке порушення правил гри з боку Вашої програми, відповідний тест (а отже, й увесь відповідний блок) оцінюватиметься як не пройдений.