Гра та сама, що у попередній задачі «Палички з ходами, залежними від попереднього», див. правила там.

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

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

Потім слід повторювати такий цикл:

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

Оцінювання

Тести оцінюються кожен окремо (без блоків).

• У 1-му тесті ~{N=3}~, у 2-му ~{N=5}~, і ці тести не приносять балів. Решта тестів приносять однакові бали.
• У 20% тестів ~{2 \leqslant N \leqslant 25}~ (~{N\neq3}~, ~{N\neq5}~), програма-суперниця ідеальна (не робить помилок).
• Ще у 20%, ~{100 < N \leqslant 1234}~, суперниця ідеальна.
• Ще у 20%, ~{1234 < N \leqslant 12345}~, суперниця ідеальна.
• Ще у 20%, ~{100 < N \leqslant 1234}~, суперниці інші.
• Ще у 20%, ~{1234 < N \leqslant 12345}~, суперниці інші.

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

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

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

Приклад 1

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

Приклад 2

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

Приклад 3

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

Приклад 4

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

Примітки

1. Всі наведені послідовності ходів є прикладами правильної гри. Ваша програма не зобов'язана при різних запусках для однієї початкової кількості паличок робити різні ходи. Але вона має таке право. Якщо Ваша програма при різних запусках грає по-різному, система автоматичної перевірки не шукатиме ні найкращий, ні найгірший з результатів, а просто оцінюватиме перший.
2. Вводити/виводити порожні рядки не треба; додаткові вертикальні відступи у прикладах зроблені умовно, щоб краще було видно, хто коли ходить.