L. Sapure
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are simulating a classic Snake game on an $$$n \times n$$$ grid.

Grid

Cells are addressed by coordinates $$$(x, y)$$$, where:

  • $$$1 \le x \le n$$$ is the row number,
  • $$$1 \le y \le n$$$ is the column number.

The snake initially consists of a single cell:

  • Head position: $$$(1, 1)$$$,
  • Initial length: $$$1$$$.

Moves

You are given a string $$$s$$$ of length $$$k$$$. Each character represents a move:

  • L: $$$(x, y) \rightarrow (x, y - 1)$$$
  • R: $$$(x, y) \rightarrow (x, y + 1)$$$
  • U: $$$(x, y) \rightarrow (x - 1, y)$$$
  • D: $$$(x, y) \rightarrow (x + 1, y)$$$
It's guaranteed no two consecutive moves are in opposite direction to each other. Formally, $$$s$$$ does not contain RL, LR, UD, or DU as a substring.

Wrapping

The grid is toroidal. If the head moves outside the grid, it reappears on the opposite side:

  • If $$$y = 0$$$, then $$$y = n$$$,
  • If $$$y = n + 1$$$, then $$$y = 1$$$,
  • If $$$x = 0$$$, then $$$x = n$$$,
  • If $$$x = n + 1$$$, then $$$x = 1$$$.

Food

There are $$$m$$$ foods given in a fixed order at positions $$$(x_i, y_i)$$$.

  • Initially, only food $$$1$$$ is present on the grid.
  • When the snake eats food $$$i$$$:
    • the snake's length increases by $$$1$$$,
    • food $$$i+1$$$ immediately appears (if $$$i \lt m$$$).
  • At any moment, at most one food exists on the grid.
  • A food is eaten if after a move the snake's head lands exactly on the current food cell.
It's guaranteed that the food will never appear on the snake's body.

Snake Movement

Each move is processed as follows:

  1. The head moves by one cell (with wrapping).
  2. If the head lands on the current food cell:
    • the snake grows (the tail does not move in this step).
  3. Otherwise:
    • the snake keeps the same length (the tail moves forward by one cell).

Death Rule

The snake dies if after moving, its head occupies a cell that is currently part of its body. If the snake does not eat during this move, moving into the current tail cell is allowed, because the tail leaves at the same time.

Task

Simulate the game for at most $$$k$$$ moves.

  • If the snake dies before completing all moves, output DEAD.
  • Otherwise, output ALIVE L, where $$$L$$$ is the final length of the snake.
Input
  • The first line contains three integers $$$n$$$, $$$k$$$, and $$$m$$$ ($$$1 \le n, k, m \le 100000$$$).
  • The second line contains a string $$$s$$$ of length $$$k$$$, consisting only of characters L, R, U, and D.
  • The next $$$m$$$ lines each contain two integers $$$x_i$$$ and $$$y_i$$$, describing the food positions in order.
Output
  • Print DEAD if the snake dies before all $$$k$$$ moves are performed.
  • Otherwise, print ALIVE L, where $$$L$$$ is the final length.
Examples
Input
3 10 3
LLDRRUURRD
1 3
2 3
3 3
Output
ALIVE 4
Input
3 5 3
RDLLL
1 2
2 2
2 1
Output
DEAD
Note

In the first sample, the grid is $$$3 \times 3$$$. The snake starts at $$$(1,1)$$$ with length $$$1$$$. Food $$$1$$$ is initially located at $$$(1,3)$$$.

The moves are: [ L, L, D, R, R, U, U, R, R, D ]

  • After L: $$$(1,1) \rightarrow (1,0)$$$ wraps to $$$(1,3)$$$. The snake eats food $$$1$$$, so its length becomes $$$2$$$. Food $$$2$$$ appears at $$$(2,3)$$$.
  • After L: $$$(1,3) \rightarrow (1,2)$$$, no food is eaten, so the tail moves.
  • After D: $$$(1,2) \rightarrow (2,2)$$$, no food is eaten, so the tail moves.
  • After R: $$$(2,2) \rightarrow (2,3)$$$. The snake eats food $$$2$$$, so its length becomes $$$3$$$. Food $$$3$$$ appears at $$$(3,3)$$$.
  • After R: $$$(2,3) \rightarrow (2,4)$$$ wraps to $$$(2,1)$$$, no food is eaten, so the tail moves.
  • After U: $$$(2,1) \rightarrow (1,1)$$$, no food is eaten, so the tail moves.
  • After U: $$$(1,1) \rightarrow (0,1)$$$ wraps to $$$(3,1)$$$, no food is eaten, so the tail moves.
  • After R: $$$(3,1) \rightarrow (3,2)$$$, no food is eaten, so the tail moves.
  • After R: $$$(3,2) \rightarrow (3,3)$$$. The snake eats food $$$3$$$, so its length becomes $$$4$$$. There are no more foods.
  • After D: $$$(3,3) \rightarrow (4,3)$$$ wraps to $$$(1,3)$$$, and no collision happens.

The snake survives all $$$10$$$ moves, so the answer is ALIVE 4.

In the second sample, the snake dies before all $$$k$$$ moves are performed.