새로운 게임

시간 제한2초메모리 제한1024 MB

요약

행렬에서 셀 값에 따라 칩을 옮기는 두 사람의 게임에서 선수가 이기는지, 후수가 이기는지, 무승부인지 판정합니다.

난이도: 보통10점 중 6점
유형: 그래프, BFS, 위상 정렬
정답자: 아직 제출이 없습니다

문제

Yasha가 종이에 $n \times m$ 크기의 수 행렬을 적고, 행렬의 한 칸에 말을 놓습니다. 플레이어는 번갈아 가며 둡니다. 말이 놓인 칸에 양수 $x$ 가 적혀 있으면, 차례인 플레이어는 말을 오른쪽으로 $x$ 칸 또는 아래로 $x$ 칸 옮길 수 있습니다. 음수 $-x$ 가 적혀 있으면, 위로 $x$ 칸 또는 왼쪽으로 $x$ 칸 옮길 수 있습니다. 말은 행렬 밖으로 나갈 수 없습니다. 둘 수 없는 플레이어는 집니다. Anton이 먼저 둡니다.

두 플레이어는 최적의 전략으로 둡니다.

입력

첫 줄에 정수 $n$ 과 $m$ ( $1 \le n, m \le 1000$ )이 주어집니다. 이어서 각 줄에 $m$ 개의 수가 적힌 줄이 $n$ 개 주어집니다. 행렬의 모든 수의 절댓값은 $1000$ 이하입니다. 마지막 줄에는 말의 초기 위치의 행 번호와 열 번호가 주어집니다(1부터 시작). 말은 처음에 행렬 안에 있다고 보장됩니다.

출력

승자가 Anton이면 "Anton", Yasha이면 "Yasha"를 출력합니다. 어느 쪽도 이길 수 없으면 "draw"를 출력합니다.

예제3

예제 1
입력
```
2 2
1 2
2 1
1 1
```
예상 출력
```
Anton
```
예제 2
입력
```
3 3
1 3 -1
3 -1 -1
1 -3 1
2 3
```
예상 출력
```
Yasha
```
예제 3
입력
```
3 3
1 1 -1
2 -1 -2
1 -2 -1
3 3
```
예상 출력
```
draw
```