A snake game runs on an R by C board (rows 0..R-1, columns 0..C-1). The snake starts as a single cell occupying (0, 0); that cell is both its head and tail. A queue of food cells must be eaten in the given order - only the food at the front of the queue is active. A move string is processed one move at a time (U/D/L/R change the head by one cell: U row-1, D row+1, L col-1, R col+1).

For each move, compute the new head cell, then:

• If the new head is outside the board, the snake dies immediately.
• Otherwise, if the new head equals the active food cell: the snake grows (its tail does not move), that food is removed from the queue, and this is valid unless the new head cell is currently occupied by the snake's body (which is a fatal self-collision).
• Otherwise (no food eaten): the tail vacates its cell as the head advances, so the snake dies only if the new head lands on a body cell other than the current tail; if it survives, the head advances and the tail moves up by one.

Once the snake dies, no further moves are processed.

Input format

Line 1: two integers R and C. Line 2: an integer F, the number of food cells. Next F lines: two integers r c each, the food cells in eating order. Next line: a non-empty move string over U, D, L, R.

Output format

A single line: ALIVE k if the snake survives every move, or DEAD k if it dies, where k is the snake's length at the end (the length reached at the moment of death if it dies).

Constraints

• 2 <= R, C <= 100
• 0 <= F <= 1000
• 1 <= move string length <= 100000

3 3
1
0 1
RD

ALIVE 2

2 2
0
RDLU

ALIVE 1