/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 400 点
問題文
H 行 W 列のマス目があり、各マスは青マスまたは赤マスのどちらかです。上から 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}
出力
高橋君が勝つなら Takahashi を、青木君が勝つなら Aoki を、引き分けになるなら Draw を出力せよ。
入力例 1
3 3 --- +-+ +--
出力例 1
Takahashi
高橋君は以下のような戦略で勝つことができます。
まず高橋君が最初に駒を右に動かします。移動先のマスは赤マスなので高橋君は 1 点を失い、高橋君と青木君の得点はそれぞれ -1, 0 となります。
- 青木君が次に駒を右に動かしたなら、高橋君は駒を下に動かします
- 青木君が次に駒を下に動かしたなら、高橋君は駒を右に動かします
いずれの場合でも青木君は赤マスに駒を動かして 1 点を失い、高橋君は青マスに駒を動かして 1 点を得るため、両者の得点はそれぞれ 0, -1 となります。
現在駒はマス目の上から 2 番目、左から 3 番目のマスにあるので、次の移動では青木君は下に動かすほかなく、移動先が赤マスなので両者の得点はそれぞれ 0, -2 となります。
もう駒は右にも下にも動かせないのでゲームは終了し、得点の大きい高橋君が勝利します。
入力例 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.