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

Напишіть програму, яка визначатиме, хто виграє при правильній грі обох гравців. Іншими словами, хто може забезпечити собі виграш, хоч би як не грав інший.

Вхідні дані

Єдине ціле число ~N~ (~1\leqslant N\leqslant 12345~) — початкова кількість паличок у купці.

Результати

Єдине ціле число, або 1 (якщо перший гравець може забезпечити собі виграш), або 2 (якщо другий).

Приклади

Вхід

2

Результат

1

Вхід

25

Результат

1

Вхід

256

Результат

2

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

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

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

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

На прямокутному полі ~N{\times}M~ клітинок у лівому верхньому кутку стоїть фішка. Ця кутова клітинка гарантовано вільна (не замінована); абсолютно кожна інша клітинка поля може бути хоч вільною, хоч замінованою. Гра полягає в тому, що два гравці поперемінно рухають згадану фішку на якусь кількість клітинок або праворуч, або донизу (кожен гравець сам вирішує, в якому з цих двох напрямків і на скільки клітинок рухати; не можна ні лишати фішку на місці, ні ставати нею в заміновану клітинку, ні перестрибувати нею через заміновану клітинку). Програє той, хто не може нікуди походити (і знизу, і праворуч або край поля, або міна). Відповідно, його суперник виграє.

Напишіть програму, яка визначатиме, хто виграє при правильній грі обох гравців. Іншими словами, хто може забезпечити собі виграш, хоч би як не грав інший.

Вхідні дані

Перший рядок містить два цілі числа ~N~ та ~M~, розділені одним пропуском (пробілом) – спочатку кількість рядків, потім кількість стовпчиків. Обидва ці значення у межах від 1 до 12.

Далі йдуть ~N~ рядків, що задають мінне поле. Кожен з них містить рівно по ~M~ символів . (позначає вільну клітинку) та/або * (позначає заміновану клітинку). Ці символи йдуть без роздільників, і кожен з цих ~N~ рядків містить лише ці символи та переведення рядка наприкінці.

Результати

Єдине ціле число, або 1 (якщо перший гравець може забезпечити собі виграш), або 2 (якщо другий).

Приклади

Вхід

2 4
....
.**.

Результат

1

Вхід

1 1
.

Результат

2

Примітки

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

У другому прикладі, першому гравцю відразу ж нема куди йти, і він негайно програє (відповідно, виграє другий гравець). Звісно, з точки зору загальнолюдських уявлень про справедливість це якась дуже нечесна гра... Але вже яка є, описані в умові задачі обмеження формально дотримані.

На прямокутному полі ~N{\times}M~ клітинок у лівому верхньому кутку стоїть фішка. Ця кутова клітинка гарантовано вільна (не замінована); абсолютно кожна інша клітинка поля може бути хоч вільною, хоч замінованою. Гра полягає в тому, що два гравці поперемінно рухають згадану фішку на якусь кількість клітинок праворуч або донизу (кожен гравець сам вирішує, в якому з цих двох напрямків і на скільки клітинок рухати; не можна ні лишати фішку на місці, ні ставати нею в заміновану клітинку, ні перестрибувати нею через заміновану клітинку). Програє той, хто не може нікуди походити (і знизу, і праворуч або край поля, або міна). Відповідно, його суперник виграє.

Напишіть програму, яка визначатиме, хто виграє при правильній грі обох гравців. Іншими словами, хто може забезпечити собі виграш, хоч би як не грав інший. Якщо виграє перший, то програма повинна знайти також сукупність усіх його виграшних перших ходів.

Вхідні дані

Перший рядок містить два цілі числа ~N~ та ~M~, розділені одним пропуском (пробілом) – спочатку кількість рядків, потім кількість стовпчиків. Обидва ці значення у межах від 1 до 2023.

Далі йдуть ~N~ рядків, що задають мінне поле. Кожен з них містить рівно по ~M~ символів . (позначає вільну клітинку) та/або * (позначає заміновану клітинку). Ці символи йдуть без роздільників, і кожен з цих ~N~ рядків містить лише ці символи та переведення рядка наприкінці.

Результати

Перший рядок має містити єдине ціле число, або 1 (якщо перший гравець може забезпечити собі виграш), або 2 (якщо другий). Якщо відповідь з першого рядка 2, то на цьому виведення слід припинити. А якщо відповідь з першого рядка 1, то далі треба вивести також перелік всіх можливих перших ходів першого гравця, після яких другий (при правильній грі першого) вже ніяк не зможе виграти. Цей перелік виводити в такому форматі: спочатку, якщо існує виграшний хід униз, то вивести його як велику латинську літеру D, одинарний пропуск (пробілом) та довжину ходу (на скільки клітинок іти вниз); потім, якщо існує виграшний хід направо, то аналогічно, але на початку велику латинську R. (Заодно доведіть, що в цій задачі не може бути багатьох виграшних ходів униз чи багатьох виграшних ходів направо.)

Приклади

Вхід

2 4
....
.**.

Результат

1
D 1
R 2

Вхід

1 1
.

Результат

2

Примітки

Спочатку детально проаналізуємо перший приклад.

Перший гравець може піти D 1 (на одну клітинку вниз), після чого другому не буде куди йти. А ще перший гравець може піти першим ходом R 2; тоді другому не лишиться ніякого вибору, крім як піти R 1 (на ще одну клітинку праворуч), після чого перший іде D 1 (вниз), і знову другому не буде куди йти.

Перший хід R 3 не виграшний, бо після нього другий гравець іде D 1 і виграє. Перший хід R 1 теж не виграшний, бо тут може бути як ситуація «другий піде R 2, перший D 1 і виграє», так і ситуація «другий піде R 1, перший не матиме іншого вибору, як іти R 1, другий піде D 1 і виграє». Тобто, в разі першого ходу першого гравця R 1 другий гравець може перехопити ініціативу, якщо зуміє. А питали перелік таких ходів, щоб другий (при правильній грі першого) вже ніяк не міг виграти.

У другому прикладі, першому гравцю відразу ж нема куди йти, і він негайно програє (відповідно, виграє другий гравець).

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

На прямокутному полі ~N{\times}M~ клітинок у лівому верхньому кутку стоїть фішка. Ця кутова клітинка гарантовано вільна (не замінована); абсолютно кожна інша клітинка поля може бути хоч вільною, хоч замінованою. Гра полягає в тому, що два гравці поперемінно рухають згадану фішку на якусь кількість клітинок праворуч або донизу (кожен гравець сам вирішує, в якому з цих двох напрямків і на скільки клітинок рухати; не можна ні лишати фішку на місці, ні ставати нею в заміновану клітинку, ні перестрибувати нею через заміновану клітинку). Програє той, хто не може нікуди походити (і знизу, і праворуч або край поля, або міна). Відповідно, його суперник виграє.

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

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

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

На початку, один раз, Ваша програма повинна прочитати поле гри. Перший рядок містить два цілі числа ~N~ та ~M~, розділені одним пропуском (пробілом) – спочатку кількість рядків, потім стовпчиків. Обидва ці значення у межах від 1 до 123.

Далі йдуть ~N~ рядків, що задають мінне поле. Кожен з них містить рівно по ~M~ символів . (позначає вільну клітинку) та/або * (позначає заміновану клітинку). Ці символи йдуть без роздільників, і кожен з цих ~N~ рядків містить лише ці символи та переведення рядка наприкінці.

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

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

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

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

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

Приклад 1

Приклад 2

Примітки

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

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

Оцінювання

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

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

Є одна купка, яка спочатку містить ~N~ паличок. Двоє грають у таку гру. Кожен з гравців на кожному своєму ході може забрати з купки деяку кількість паличок (звісно, не більше, чим їх є в купці), причому кількості паличок, які можна забирати, для різних суперників різні: 1-й гравець може забирати або 4, або 8, або 16, або 32 палички, тоді як 2-й – або 2, або 7, або 14. Ніяких інших варіантів ходу нема. Ходять гравці по черзі, пропускати хід не можна. Програє той, хто не може походити. Зверніть увагу: оскільки в цій задачі гравці не можуть забирати 1 паличку, можливі також і ситуації, коли палички ще є, а походити вже не можна. Точніше кажучи, 1-й вже не може ходити не лише коли йому не лишили паличок, але також і коли лишили 1, 2 або 3 палички; 2-й вже не може ходити не лише коли йому не лишили паличок, але також і коли лишили 1 паличку.

Вхідні дані

Єдине ціле число ~N~ (~1\leqslant N\leqslant 12345~) – початкова кількість паличок у купці.

Результати

Перший рядок має містити єдине ціле число, або 1 (якщо перший гравець може забезпечити собі виграш), або 2 (якщо другий). Якщо відповідь з першого рядка 2, то на цьому виведення слід припинити. А якщо відповідь з першого рядка 1, то далі треба вивести також перелік всіх можливих перших ходів першого гравця, після яких другий (при правильній грі першого) вже ніяк не зможе виграти. Цей перелік виводити в такому форматі: вибрати лише потрібні числа з переліку допустимих ходів 4, 8, 16, 32, і записати в другому рядку всі вибрані («виграшні») в порядку зростання через пробіли. Кількість «виграшних ходів» виводити не треба і не можна.

Приклади

Вхід

7

Результат

2

Вхід

10

Результат

1
4

Примітки

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

У другому тесті, у 1-го гравця на першому ході фактично є вибір «забирати 4 чи забирати 8», причому якщо він забере 8, то 2-й забере 2 палички і тим виграє, бо 1-му гравцю нема паличок і тому нема ходів. (Отже, 1-му гравцю не варто забирати 8 на своєму першому ході.) А от якщо 1-й гравець на першому ході здогадається забрати 4 палички (залишиться 6), то у 2-го нема вибору (може лише забрати 2 палички, лишається 4), після чого 1-й гравець може забрати 4 палички і тим виграти, бо 2-му гравцю нема паличок і тому нема ходів.

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

На прямокутному полі ~N{\times}M~ клітинок у лівому верхньому кутку стоїть фішка. Ця кутова клітинка гарантовано вільна (не замінована); абсолютно кожна інша клітинка поля може бути хоч вільною, хоч замінованою. Гра полягає в тому, що два гравці поперемінно рухають згадану фішку на якусь кількість клітинок праворуч або донизу (кожен гравець сам вирішує, в якому з цих двох напрямків і на скільки клітинок рухати; не можна ні лишати фішку на місці, ні ставати нею в заміновану клітинку, ні перестрибувати нею через заміновану клітинку). \Виграє той, хто не може нікуди походити (і знизу, і праворуч або край поля, або міна). Відповідно, його суперник програє.

Напишіть програму, яка визначатиме, хто виграє при правильній грі обох гравців. Іншими словами, хто може забезпечити собі виграш, хоч би як не грав інший.

Вхідні дані

Перший рядок містить два цілі числа ~N~ та ~M~, розділені одним пропуском (пробілом) – спочатку кількість рядків, потім кількість стовпчиків. Обидва ці значення у межах від 1 до 12.

Далі йдуть ~N~ рядків, що задають мінне поле. Кожен з них містить рівно по ~M~ символів . (позначає вільну клітинку) та/або * (позначає заміновану клітинку). Ці символи йдуть без роздільників, і кожен з цих ~N~ рядків містить лише ці символи та переведення рядка наприкінці.

Результати

Єдине ціле число, або 1 (якщо перший гравець може забезпечити собі виграш), або 2 (якщо другий).

Приклади

Вхід

2 4
....
.**.

Результат

1

Вхід

1 1
.

Результат

1

Примітки

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

Тому, слово «навпаки» вжите в назві задачі для того, щоб підкреслити: дуже часто геть не ясно, що взагалі таке «навпаки». Завершити ж усе це хочемо відомою «цитатою зі шкільного учнівського твору»: «на березі річки доярка доїла корову, а у воді відображалось усе навпаки».