Змійка#11061

Змійка

1 секунда

128 мегабайтів

Дуже легка

Розбираючи одну зі скринь удома, Карич знайшов старий кнопковий телефон. На цьому телефоні була лише одна гра, але яка! Змійка! Карич багато грав у неї, наприклад, їдучи у поїзді чи стоячи у черзі.

Гра проходить на прямокутному полі розміром $n \times m$ n \times m. Поле не зациклене ні по вертикалі, ні по горизонталі. Тобто, якщо змійка вріжеться в межу поля, гра закінчується програшем. Рядки поля пронумеровані від $1$ до $n$ зверху вниз, а стовпці — від $1$ до $m$ зліва направо.

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

На кожному ході гравець повинен вибрати один з чотирьох напрямків руху: вгору, вниз, вліво або вправо. Після цього гра знаходить сусідню з головою змійки клітинку в обраному гравцем напрямку. Назвемо її $q$ .

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

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

На початку гри змійка має довжину $1$ .

Карич чув, що якщо виграти у цій грі, тобто заповнити змійкою всі клітинки поля, то гра покаже мультик. Але йому ніколи не вдавалося це зробити. Допоможіть йому! Ви повинні зробити не більше $100000$ ходів.

Взаємодія

У першому рядку задано два цілі числа $n$ і $m$ ( $2 \leq n, m \leq 10$ 2 \le n, m \le 10) —розміри поля.

У другому рядку два цілі числа $x_{s}$ x_s і $y_{s}$ y_s ( $1 \leq x_{s} \leq n$ 1 \le x_s \le n, $1 \leq y_{s} \leq m$ 1 \le y_s \le m) —номер рядка і стовпця, у перетині яких знаходиться клітинка змійки на початку гри.

У третьому рядку два цілі числа $x_{a}$ x_a і $y_{a}$ y_a ( $1 \leq x_{a} \leq n$ 1 \le x_a \le n, $1 \leq y_{a} \leq m$ 1 \le y_a \le m) —координати клітинки, у якій на початку гри знаходиться яблуко.

Далі ви повинні взаємодіяти з тестуючою програмою. На кожному ході ви повинні вивести один із символів, що позначають напрямок руху: "U" (вгору), "D" (вниз), "L" (вліво) або "R" (вправо).

Після цього програма виведе одну з кількох можливих відповідей:

- "fail" — означає, що змійка врізалася у стіну, з'їла себе або у вас закінчилися ходи, але ви не виграли. У такому випадку ви повинні негайно завершити виконання програми, щоб отримати вердикт WA. Інакше ви можете отримати інший вердикт (не AC). - "win" — довжина змійки стала рівною $n \times m$ n \times m, ви виграли. Потрібно, не виводячи більше нічого, завершити виконання програми. - "ok" — ви зробили коректний хід. У результаті, голова змійки змістилася в обраному вами напрямку, довжина змійки не змінилася. - "new" — ви зробили коректний хід і змійка з'їла яблуко. Голова змійки змістилася в обраному напрямку, довжина змійки збільшилася на $1$ . У наступному рядку буде два цілих числа $x_{a}$ x_a і $y_{a}$ y_a ( $1 \leq x_{a} \leq n$ 1 \le x_a \le n, $1 \leq y_{a} \leq m$ 1 \le y_a \le m) —координати нового місця яблука.

Гарантується, що в будь-який момент часу яблуко буде розташоване у клітинці, яка не належить змійці.

Не забувайте після кожного виводу переходити на новий рядок та скидати буфер виводу.