Snake Game

A snake crawls around a board that is height rows tall and width columns wide. Squares are (row, col), with (0, 0) in the top left corner. The snake starts as a single square at (0, 0). moves is a string of 'U', 'D', 'L' and 'R' (up, down, left, right), one letter per move. food is a list of squares: only the first one is on the board at the start, and each time the snake eats, the next one in the list appears. After the last one is eaten, no more food appears.

On every move, in this order:

• The head moves one square in the given direction. If it leaves the board, the snake crashes.
• If the head is now on the food, the snake eats it: the score goes up by 1, the snake grows by one square (its tail stays where it is on this move) and the next food appears. Otherwise the tail moves along: the snake's last square is freed.
• If the head is now on a square covered by the rest of the snake, the snake crashes.

So the head may move into the square that the tail leaves on the same move, even when the snake turns straight back: a snake of 2 squares that reverses does not crash, because its head moves into the square its tail is leaving. A longer snake that turns straight back crashes, because its head lands on the second square of its body. Write snake(width, height, moves, food) that returns a tuple (score, crash): the number of foods eaten, and the number of the move on which the snake crashed (moves are numbered from 1), or 0 if it never crashed. Nothing happens after a crash.

Examples

snake(3, 3, 'RRDLU', [(0, 1), (0, 2), (1, 2), (1, 1)])    # returns (4, 5)
snake(4, 2, 'RRRRR', [])                                 # returns (0, 4)
snake(2, 2, 'RDLURDLU', [(0, 1), (1, 1), (1, 0)])        # returns (3, 0)
snake(4, 1, 'RRL', [(0, 1)])                             # returns (1, 0)

In the first example the snake eats on each of its first four moves and is 5 squares long; moving up then puts its head on its own body. In the second, the fourth move leaves the 4-column board. In the third, a snake of 4 squares chases its own tail around a 2 by 2 board without ever crashing. In the fourth, the snake is 2 squares long when it turns back to the left, and it does not crash.

Constraints

• 1 <= width, height <= 300; moves has up to 100,000 letters.
• A food never appears on a square the snake covers at that moment.