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

Ця задача відрізняється від задачі «Нім — інтерактив» в точності тим, що за один хід можна забирати не більше 3-х паличок.

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

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

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

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

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

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

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

1. Вивести два числа, розділені пропуском, у окремому рядку – свій хід, тобто номер купки, з якої вона забирає палички, та кількість паличок, які вона забирає. Це повинно бути ціле число від 1 до 3 (обидві межі включно) і не перевищувати поточної кількості паличок у відповідній купці. Купки занумеровані з одиниці: 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). Це істотно зменшує ризик, що проміжна відповідь «загубиться» десь по дорозі, не дійшовши до програми-суперниці.

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

Примітки

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

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

У звичайному Німі (без обмеження на кількість паличок, які можна забирати за один раз) Вашій програмі варто було б почати з ходу 2 4, після якого лишилося б (4,4). Однак, у цій задачі не можна забирати відразу 4 палички, тому такий хід неможливий.

Оцінювання

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

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