Змейка
Вася очень любит играть в компьютерную игру "Змейка". В ней игрок управляет длинным тонким существом, напоминающем змею, которое ползает по прямоугольному полю с шириной N и высотой M, окруженному со всех сторон стенками. Сама змейка состоит из L звеньев, каждое из которых занимает одну клетку поля. Любые два последовательных звена змейки должны находиться в соседних одна с другой клетках, и змейка не должна иметь самопересечений (то есть никакие два звена змейки не могут располагаться в одной клетке). Змейка все время движется и игрок не может ее остановить, но можно изменять направление ее движения с помощью курсорных клавиш. Чем дольше игроку удастся управлять змейкой, избегая самопересечений и врезания в стены, тем больше очков он заработает. Перемещение змейки осуществляется таким образом, что ее первое звено (голова) займет клетку, соседнюю с предыдущим его положением в направлении, соответствующем нажатой курсорной клавиши. Каждое последующее звено в новом положении змейки занимает ту клетку, которую занимало предыдущее звено в старом положении. Таким образом сохраняется связность змейки. Клетка, которую в старом положении занимало последнее звено (хвост), станет свободной (если только в ней не окажется теперь голова змейки). В случае, если никакая клавиша не нажималась, голова змейки будет двигаться в ту же сторону, что и при предыдущем перемещении.
Во время очередной игры Васе понадобилось отлучиться от компьютера, но игру он не выключил, поэтому змейка теперь движется без управления.
Напишите программу, которая определит количество перемещений змейки до того, как она столкнется со стеной или с какой-то своей частью.
Входные данные
В первой строке задаются 2 целых чисел: размеры поля N (по оси Ox) и M (по оси Oy) (2 ≤ N, M ≤ 1000). Во второй строке задаются координаты x, y (1 ≤ x ≤ N, 1 ≤ y ≤ M) клетки, в которой находится хвост змейки, и ее длина L (2 ≤ L ≤ NM). Третья строка состоит из L-1 символов, не разделяемых пробелами, которые определяют последовательность направлений перемещений змейки до ухода Васи. Символ U обозначает, что соответствующее перемещение происходило вверх, D - вниз, L - влево, R - вправо. Ось Ox считается направленной вправо, ось Oy - вверх, клетка, граничащая с левой и нижней стенами, имеет координаты (1, 1). Гарантируется, что змейка на момент ухода занимала допустимое положение.
Выходные данные
В первой строке выведите слово "WALL", если произойдет столкновение со стеной, или слово "BODY", если змейка столкнется сама с собой. Во второй строке выведите сколько раз успеет переместиться змейка до того, как произойдет один из указанных вариантов.