配点 : $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 を出力せよ。

3 3
---
+-+
+--

Takahashi

高橋君は以下のような戦略で勝つことができます。

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

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

いずれの場合でも青木君は赤マスに駒を動かして $1$ 点を失い、高橋君は青マスに駒を動かして $1$ 点を得るため、両者の得点はそれぞれ $0, -1$ となります。 現在駒はマス目の上から $2$ 番目、左から $3$ 番目のマスにあるので、次の移動では青木君は下に動かすほかなく、移動先が赤マスなので両者の得点はそれぞれ $0, -2$ となります。 もう駒は右にも下にも動かせないのでゲームは終了し、得点の大きい高橋君が勝利します。

2 4
+++-
-+-+

Aoki

青木君は、高橋君がどのように操作しても、上手く操作すれば勝つことができます。

1 1
-

Draw

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