Contest Duration: - (local time) (100 minutes) Back to Home
D - Game in Momotetsu World /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

HW 列のマス目があり、各マスは青マスまたは赤マスのどちらかです。上から i 番目、左から j 番目のマスは、A_{i, j}+ なら青マスであり、- なら赤マスです。

2 人の得点は最初 0 点ずつです。2 人は、高橋君から始めて交互に次の操作をします。

• 駒を一つ右または一つ下のマスに動かす。ただし、駒がマス目の外に出るような動かし方はできない。動かした人は、駒の移動後のマスが青マスなら 1 点を得て、赤マスなら 1 点を失う。

どちらかが操作できなくなった時点でゲームは終了します。ゲームの結果は、終了時の 2 人の得点が異なるならば得点の大きい方が勝ち、同じならば引き分けとなります。

### 制約

• 1 \le H, W \le 2000
• A_{i, j}+ または -

### 入力

H W
A_{1, 1}A_{1, 2}A_{1, 3} \dots A_{1, W}
A_{2, 1}A_{2, 2}A_{2, 3} \dots A_{2, W}
A_{3, 1}A_{3, 2}A_{3, 3} \dots A_{3, W}
\hspace{2cm}\vdots
A_{H, 1}A_{H, 2}A_{H, 3} \dots A_{H, W}


### 入力例 1

3 3
---
+-+
+--


### 出力例 1

Takahashi


まず高橋君が最初に駒を右に動かします。移動先のマスは赤マスなので高橋君は 1 点を失い、高橋君と青木君の得点はそれぞれ -1, 0 となります。

• 青木君が次に駒を右に動かしたなら、高橋君は駒を下に動かします
• 青木君が次に駒を下に動かしたなら、高橋君は駒を右に動かします

いずれの場合でも青木君は赤マスに駒を動かして 1 点を失い、高橋君は青マスに駒を動かして 1 点を得るため、両者の得点はそれぞれ 0, -1 となります。

もう駒は右にも下にも動かせないのでゲームは終了し、得点の大きい高橋君が勝利します。

### 入力例 2

2 4
+++-
-+-+


### 出力例 2

Aoki


### 入力例 3

1 1
-


### 出力例 3

Draw


この場合ゲームは直ちに終了し、両者得点 0 であるため結果は引き分けとなります。

Score : 400 points

### Problem Statement

We have a grid with H rows and W columns of squares, where each square is blue or red. The square at the i-th row and j-th column is blue if A_{i, j} is +, and red if A_{i, j} is -.
There is a piece on this grid, which is initially placed on the top-left square. Takahashi and Aoki will play a game using this piece.
Each of the two players has 0 points in the beginning. They will alternately do the following operation, with Takahashi going first:

• Move the piece one square right or one square down. It is not allowed to move the piece outside the grid. Then, the player (who moved the piece) gets one point if the piece is now on a blue square, and loses one point if the piece is now on a red square.

The game ends when one of the players is unable to do the operation. Then, the player with the greater number of points wins the game if they have different numbers of points. Otherwise, the game is drawn.
Find the result of the game when both players play the game to get the best outcome.

### Constraints

• 1 \le H, W \le 2000
• A_{i, j} is + or -.

### Input

Input is given from Standard Input in the following format:

H W
A_{1, 1}A_{1, 2}A_{1, 3} \dots A_{1, W}
A_{2, 1}A_{2, 2}A_{2, 3} \dots A_{2, W}
A_{3, 1}A_{3, 2}A_{3, 3} \dots A_{3, W}
\hspace{2cm}\vdots
A_{H, 1}A_{H, 2}A_{H, 3} \dots A_{H, W}


### Output

If Takahashi will win, print Takahashi; if Aoki will win, print Aoki; if the game will be drawn, print Draw.

### Sample Input 1

3 3
---
+-+
+--


### Sample Output 1

Takahashi


Takahashi has a winning strategy described below.

First, Takahashi moves the piece right, which makes him lose one point because the piece goes to a red square. Now, Takahashi has -1 point and Aoki has 0 points. Then,

• if Aoki moves the piece right, Takahashi moves it down;
• if Aoki moves the piece down, Takahashi moves it right.

In either case, Aoki moves the piece to a red square losing one point, and Takahashi moves the piece to a blue square getting one point, which means now Takahashi has 0 points and Aoki has -1 point.
The piece is now on the square at the 2-nd row from the top and 3-rd column from the left, and Aoki can only choose to move it down, to a red square. Now, Takahashi has 0 points and Aoki has -2 points.
The piece cannot move right or down anymore, so the game ends. Since Takahashi has the greater number of points, he wins.

### Sample Input 2

2 4
+++-
-+-+


### Sample Output 2

Aoki


Aoki can win the game, regardless of what choices Takahashi makes.

### Sample Input 3

1 1
-


### Sample Output 3

Draw


In this case, the game immediately ends. Since both players have 0 points, the game is drawn.