25598번 - Alive or Dead?

해강이는 게임을 좋아한다. 그래서 직접 게임을 만들어 친구인 영재에게 자신이 만든 게임을 해보라고 권했다. 게임을 해본 영재는 게임 결과를 빨리 알고 싶어 했다. 참을성이 없는 영재에게 게임의 결과를 알려주자!

다음은 해강이가 만든 게임에 대한 설명이다.

1. 게임은 $N \times N$ 2차원 격자에서 진행이 된다.
2. 플레이어의 시작 위치는 $(p_y,\,p_x)$이다. 위에서부터 $p_y$번째 줄, 왼쪽에서 $p_x$번째 줄에 있다는 뜻이다. $(p_x,\,p_y)$가 아님에 유의하라.
3. 플레이어는 명령어를 하루에 한 번 실행한다.
   1. 명령어는 대문자 '$U$', '$D$', '$L$', '$R$', '$S$'로 5가지이다. 각각 위로 한 칸 이동, 아래로 한 칸 이동, 왼쪽으로 한 칸 이동, 오른쪽으로 한 칸 이동, 제자리에 있음을 의미한다.
   2. 이동하려는 위치가 게임 필드를 벗어나거나 벽인 경우에는 이동하지 않는다.
4. 각 칸에 벽이 있을 수 있다.
   1. 벽의 위치는 $(w_y,\,w_x)$로 주어진다. 위에서부터 $w_y$번째 줄, 왼쪽에서 $w_x$번째 줄에 있다는 뜻이다.
5. 플레이어를 위협하는 좀비도 존재한다.
   1. 플레이어의 명령어 실행이 끝나면 좀비들이 정해진 순서로 한 번에 한 마리씩 이동한다.
   2. 좀비의 위치는 $(z_y,\,z_x)$로 주어진다. 위에서부터 $z_y$번째 줄, 왼쪽에서 $z_x$번째 줄에 있다는 뜻이다.
   3. 좀비의 종류는 하급 좀비와 상급 좀비가 있다.
   4. 다음은 하급 좀비에 대한 설명이다.
      1. 하급 좀비는 매일 현재 바라보고 있는 방향으로 한 칸씩 $l$번 이동한다.
      2. 단, 이동하려는 위치가 게임 필드를 벗어나거나 벽인 경우에는 $l$번을 다 이동하지 않고 정지한 뒤, 현재 방향의 반대로 방향을 튼다. 남은 이동 횟수 만큼 다시 이동하지 않음에 유의하라.
   5. 다음은 상급 좀비에 대한 설명이다.
      1. 상급 좀비는 매일 현재 바라보고 있는 방향으로 한 칸씩 $h$번 이동한다.
      2. 단, 이동하려는 위치가 게임 필드를 벗어나거나 벽인 경우에는 $h$번을 다 이동하지 않고 정지한다. 또한 벽에 막혔을 경우 벽 앞에서 정지하며, 좀비가 벽을 부숴서 그 벽은 사라진다.
      3. 그 후, 중간에 정지했는지 여부와 관계없이 정지한 뒤, 상하좌우 방향 중 벽의 개수를 세어 벽이 가장 많은 방향으로 방향을 튼다. 만약 벽의 개수가 같은 경우는 '상', '우', '하', '좌' 우선 순위로 방향을 튼다.

      4. 상급 좀비가 벽의 개수를 셀 때는 해당 상급 좀비가 벽을 무시하고 게임 필드 경계까지 이동했을 때, 만나게 되는 벽의 개수를 센다.

         

         위 그림은 상급 좀비가 상, 하, 좌, 우 방향으로 벽을 세는 모습이다.

   6. 좀비가 이동과 방향 변경을 마치면 다음 좀비의 이동이 시작된다. 좀비들의 이동 순서는 생성(입력)된 순으로 진행된다.
6. 모든 좀비의 이동이 끝난 뒤, 한 칸에 여러 마리의 좀비가 있을 수 있다.
7. 다음은 플레이어와 좀비의 이동이 모두 끝난 뒤의 설명이다.
   1. 만약 플레이어와 좀비가 같은 칸에 있는 경우, 플레이어는 죽게 되고 게임은 종료된다.
   2. 만약 플레이어와 좀비가 같은 칸에 있지 않은 경우, 다음 날로 넘어간다.
8. 좀비가 이동 중에 플레이어를 만나도 플레이어를 죽이지 않는다.

영재는 플레이어의 $D$일차의 생존 여부를 알고 싶어 한다.

첫 번째 줄에 게임 필드의 크기 $N$이 주어진다. $(3 \le N \le 25)$ 

두 번째 줄에 영재가 플레이어를 움직일 명령어 $O$개가 공백 없이 주어진다. $(1 \le O \le 10 ^ 4)$

세 번째 줄에는 플레이어의 시작 위치 $p_y$, $p_x$가 공백으로 구분되어 주어진다. $(1 \le p_y, p_x \le N)$

네 번째 줄에는 벽의 개수 $W$가 주어진다. $(0 \le W \le N^2 - 1)$

다음 $W$개의 줄에 걸쳐 벽의 위치 $w_y$, $w_x$가 공백으로 구분되어 주어진다. 벽은 한 칸에 한 개만 존재한다. 벽은 플레이어의 시작 위치에 존재하지 않는다. $(1 \le w_y, w_x \le N)$ 

$W+5$번째 줄에 좀비의 수 $Z$가 주어진다. $(0 \le Z \le N^2 - 1 - W)$ 

다음 $Z$개의 줄에 걸쳐 좀비의 위치 $z_y$, $z_x$와 좀비의 종류, 좀비의 이동 방향, 좀비의 속도가 공백으로 구분되어 주어진다. 좀비는 플레이어의 시작 위치 또는 벽의 위치에 존재하지 않는다. 좀비는 한 칸에 한 마리만 생성된다. $(1 \le z_y, z_x \le N)$ 

• 좀비의 종류는 $0$(하급), $1$(상급)으로 주어진다
• 좀비의 방향은 대문자 '$U$', '$D$', '$L$', '$R$' 4가지이고 각각 상, 하, 좌, 우를 의미한다.
• 만약 하급 좀비라면 속도는 하루에 $l$칸 $(0 \le l \le N)$, 상급 좀비라면 하루에 $h$칸 $(0 \le h \le 10^8)$으로 주어진다.

$W + Z + 6$번째 줄에 영재가 알고 싶어하는 게임의 일차인 자연수 $D$가 주어진다. $(1 \le D \le O)$

만약 $D$일차가 끝난 뒤 플레이어가 살아있으면 "ALIVE!"를 출력한다.

플레이어가 죽었으면, 플레이어가 죽은 일차를 출력하고 그 다음 줄에 "DEAD..."를 출력한다.