Snake#1677
Vasya is a fan of the computer game "Snake". In this game, the player maneuvers a snake-like creature across a rectangular field with a width of and a height of , bordered by walls. The snake is made up of segments, each occupying one cell on the field. Any two consecutive segments must be in adjacent cells, and the snake cannot overlap itself (that is, no two segments can share the same cell). The snake moves continuously; the player cannot stop it, but can change its direction using the arrow keys. The longer the player avoids collisions with the walls or the snake itself, the more points they score. The snake moves so that its first segment (the head) occupies a cell adjacent to its previous position, in the direction of the last pressed arrow key. Each subsequent segment moves into the cell previously occupied by the segment ahead of it, so that the snake remains connected. The cell that was occupied by the final segment (tail) in the previous position becomes free, unless the head moves into it. If no key is pressed, the head continues moving in the same direction as before.
During one game session, Vasya had to leave the computer unattended, so now the snake moves on its own.
Write a program to determine how many moves the snake will make before it collides with a wall or with itself.
The first line contains two integers: the dimensions of the field (along the axis) and (along the axis) (2 \leq N, M \leq 1000). The second line contains the coordinates , (1 \leq x \leq N, 1 \leq y \leq M) of the cell where the snake's tail is located, and its length (2 \leq L \leq NM). The third line contains L-1 characters, without spaces, denoting the sequence of the snake's movements before Vasya left. The character means upward movement, means downward, means left, and means right. The axis is directed to the right, the axis is directed upwards, and the cell adjacent to the left and bottom boundaries has coordinates . It is guaranteed that the snake was in a valid position when Vasya left.
On the first line, output WALL if the snake crashes into a wall, or BODY if it collides with itself. On the second line, output the number of moves the snake will make before one of these events occurs.
Example 1