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

Гра в точності та ж, що в попередній задачі «Викреслювання клітинок — 1»; за тим посиланням наведено також пару прикладів для пояснення правил (можливих ходів).

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

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

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

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

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

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

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

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

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

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

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

Примітки

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

Загальний хід гри з прикладу можна прокоментувати так:

Оцінювання

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

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