Snake
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 N and a height of M, bordered by walls. The snake is made up of L segments, each occupying one cell on the field. Consecutive segments must be in adjacent cells, and the snake cannot overlap itself (i.e., no two segments can share the same cell). The snake moves continuously, and while the player cannot stop it, they can change its direction using arrow keys. The longer the player avoids collisions with walls or the snake itself, the more points they score. The snake moves such that its head occupies a cell adjacent to its previous position, following the direction of the last pressed arrow key. Each subsequent segment moves into the cell previously occupied by the segment ahead of it, maintaining the snake's connectivity. The cell vacated by the tail becomes free unless the head moves into it. If no key is pressed, the snake continues in its last direction.
During one game session, Vasya had to leave the computer, leaving the snake to move on its own.
Write a program to determine how many moves the snake will make before it hits a wall or collides with itself.
Input
The first line contains 2 integers: the dimensions of the field N (along the Ox axis) and M (along the Oy axis) (2 ≤ N, M ≤ 1000). The second line provides the coordinates x, y (1 ≤ x ≤ N, 1 ≤ y ≤ M) of the cell where the snake's tail is located, and its length L (2 ≤ L ≤ NM). The third line contains L-1 characters, without spaces, indicating the sequence of the snake's movements before Vasya left. The character U denotes an upward move, D a downward move, L a leftward move, and R a rightward move. The Ox axis points to the right, the Oy axis points upwards, and the cell adjacent to the left and bottom walls has coordinates (1, 1). It is guaranteed that the snake was in a valid position when Vasya left.
Output
On the first line, print "WALL" if the snake collides with a wall, or "BODY" if it collides with itself. On the second line, print the number of moves the snake will make before one of these events occurs.