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

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

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

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

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

На початку, один раз, Ваша програма повинна прочитати одне ціле число в окремому рядку – початкову кількість паличок ~N~ (~1{\leqslant}N{\leqslant}12345~). Потім вона повинна повторювати такий цикл:

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

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

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

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

Примітки

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

Загальний хід гри з прикладу можна прокоментувати так. У купці спочатку 5 паличок. Ваша програма забирає одну, лишається 4; програма-суперниця забирає дві, лишається 2; Ваша програма забирає обидві, повідомляє про свій виграш і завершує роботу.

Оцінювання

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

Тобто, щоб отримати абсолютно повні бали, Ваша програма має врахувати все щойно перелічене. Конкретно в цій задачі, можливі часткові бали як у смислі «одні тести успішно пройдені, інші ні», так і в смислі часткових балів за окремо взятий тест. Часткові бали за окремий тест можливі, коли програма грала з дотриманням усіх правил і вчасно завершила гру, але програла, коли можна було виграти, та/або вивела неправильне повідомлення про завершення гри чи не вивела його взагалі, тощо.

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