Змійка#1677

Змійка

1 секунда

64 мегабайти

Легка

Вася — шанувальник комп'ютерної гри «Змійка». У цій грі гравець керує істотою, схожою на змію, по прямокутному полю шириною $N$ і висотою $M$ , обмеженому стінами. Змія складається з $L$ сегментів, кожен з яких займає одну клітинку на полі. Будь-які два сусідні сегменти мають бути в сусідніх клітинках, і змія не може перетинати саму себе (тобто жодні дві частини змії не можуть займати одну і ту ж клітинку). Змія рухається безперервно; гравець не може її зупинити, але може змінювати її напрямок за допомогою клавіш зі стрілками. Чим довше гравець уникає зіткнень зі стінами або зі змією, тим більше балів він набирає. Змія рухається так: її перший сегмент (голова) займає клітинку, сусідню з її попереднім положенням, у напрямку останньої натиснутої стрілки. Кожен наступний сегмент переходить у клітинку, яку займав попередній сегмент, щоб зберігати цілісність змії. Клітинка, яку займав останній сегмент (хвіст) у попередній позиції, стає вільною, якщо тільки голова не зайшла в неї. Якщо жодна клавіша не натиснута, голова продовжує рухатися у попередньому напрямку.

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

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

Вхідні дані

У першому рядку задано два числа: розміри поля $N$ (уздовж осі $O x$ ) і $M$ (уздовж осі $O y$ ) ( $2 \leq N, M \leq 1000$ 2 \leq N, M \leq 1000). У другому рядку вказані координати $x$ , $y$ ( $1 \leq x \leq N$ 1 \leq x \leq N, $1 \leq y \leq M$ 1 \leq y \leq M) клітинки, в якій знаходиться хвіст змії, та її довжина $L$ ( $2 \leq L \leq N M$ 2 \leq L \leq NM). У третьому рядку задано $L - 1$ L-1 символів, без пробілів, що позначають послідовність рухів змії до того, як Вася відійшов. Символ $U$ означає рух вгору, $D$ — вниз, $L$ — вліво, $R$ — вправо. Вісь $O x$ спрямована вправо, вісь $O y$ — вгору, а клітинка біля лівої та нижньої меж має координати $(1, 1)$ . Гарантується, що на момент, коли Вася відійшов, змія займала коректну позицію.

Вихідні дані

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

Приклади

Приклад 1