Deadly School Route

Jihun moves along his school route by stepping only on paving blocks of the same color. He dies if he steps on a block of a different color.

The route can be represented as an $N \times M$ matrix, and each element of the matrix is one paving block. Jihun starts at row 1, column 1 and must arrive at row $N$, column $M$.

While moving along a route made of red or gray blocks, Jihun must step only on blocks with the same color as the block he is currently standing on. His jump power is $X$, so he can move only between blocks whose Manhattan distance is at most $X$. Determine whether Jihun can reach school alive.

The first line contains the number of rows $N$ $(2 \le N\le 100)$. The second line contains the number of columns $M$ $(2 \le M\le 100)$. The next $N$ lines each contain $M$ integers separated by spaces, where the $i$-th of these lines gives the colors of the blocks in row $i$ from left to right. $0$ means a red block and $1$ means a gray block. The last line contains Jihun's jump power $X$ $(1 \le X \le 10)$.

Print ALIVE if Jihun can complete the trip alive, otherwise print DEAD.

The Manhattan distance between the block at row $x\_1$, column $y\_1$ and the block at row $x\_2$, column $y\_2$ is defined as $\lvert x\_1 - x\_2 \rvert + \lvert y\_1 - y\_2 \rvert$.