죽음의 등굣길

지훈이는 등굣길에서 보도블록을 지날 때 같은 색의 보도블록만 밟으며 이동한다. 다른 색의 보도블록을 밟으면 사망하기 때문이다.

등굣길은 $N \times M$ 크기의 행렬로 표현할 수 있으며, 행렬의 각 원소는 보도블록 하나에 해당한다. 지훈이는 $1$행 $1$열에서 출발해 $N$행 $M$열에 도착해야 한다.

빨간색 또는 회색으로 이루어진 등굣길을 이동하면서 지훈이는 현재 밟고 있는 보도블록과 같은 색의 보도블록만 밟고 이동해야 한다. 또한 점프력이 $X$이므로, 맨해튼 거리가 $X$ 이하인 보도블록으로만 이동할 수 있다. 지훈이가 무사히 등교를 마칠 수 있는지 알아보자.

첫째 줄에 등굣길의 행의 개수 $N$이 주어진다. $(2 \le N\le 100)$ 둘째 줄에는 열의 개수 $M$이 주어진다. $(2 \le M\le 100)$ 셋째 줄부터 $N$개의 줄에 걸쳐 $i$번째 줄에는 $i$번째 행의 보도블록 색깔을 나타내는 $M$개의 정수가 열 순서대로 공백으로 구분되어 주어진다. $0$은 빨간색 보도블록, $1$은 회색 보도블록을 의미한다. 마지막 줄에는 지훈이의 점프력을 나타내는 정수 $X$가 주어진다. $(1 \le X \le 10)$

지훈이가 살아서 등교에 성공할 수 있으면 ALIVE, 그렇지 않으면 DEAD를 출력한다.

$x\_1$행 $y\_1$열에 있는 보도블록과 $x\_2$행 $y\_2$열에 있는 보도블록 사이의 맨해튼 거리는 $\lvert x\_1 - x\_2 \rvert + \lvert y\_1 - y\_2 \rvert$로 정의한다.