New Game

Time limit2sMemory limit1024 MB

Summary

Two players move a chip on a matrix according to cell values; decide whether the first player wins, the second player wins, or the game is a draw.

Level: Medium6 of 10
Topics: Graph, BFS, Topological sort
Solved: No attempts yet

Statement

Yasha writes an $n \times m$ matrix of numbers on a sheet and places a chip in one of its cells. Players move in turns. If the cell with the chip contains a positive number $x$ , the player to move may shift the chip $x$ cells to the right or $x$ cells down. If the cell contains a negative number $-x$ , the player may shift the chip $x$ cells up or $x$ cells to the left. The chip cannot leave the matrix. A player who cannot move loses. Anton moves first.

Both players play optimally.

Input

Input: the first line contains two integers $n$ and $m$ ( $1 \le n, m \le 1000$ ), the matrix size. Then follow $n$ lines with $m$ numbers each. All numbers in the matrix have absolute value at most $1000$ . The last line contains the initial row and column of the chip, both 1-indexed. The chip starts inside the matrix.

Output

Output one of the following: "Anton" if Anton wins, "Yasha" if Yasha wins, or "draw" if neither player can force a win.

Examples3

Example 1
Input
```
2 2
1 2
2 1
1 1
```
Expected output
```
Anton
```
Example 2
Input
```
3 3
1 3 -1
3 -1 -1
1 -3 1
2 3
```
Expected output
```
Yasha
```
Example 3
Input
```
3 3
1 1 -1
2 -1 -2
1 -2 -1
3 3
```
Expected output
```
draw
```