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

На прямокутному полі ~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

Примітки

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

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

Оцінювання

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

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