桃铁世界中的游戏

题目描述

有一个 $H$ 行 $W$ 列的方格棋盘，每个格子为蓝色或红色。第 $i$ 行第 $j$ 列的格子，当 $A_{i,j}$ 为 + 时是蓝色，为 - 时是红色。

棋盘上有一枚棋子，初始放在左上角。高桥君和青木君用这枚棋子进行游戏。

两位玩家初始都有 0 分。他们轮流执行以下操作，高桥君先手：

• 将棋子向右或向下移动一格，不能移出棋盘。然后，移动棋子的玩家获得 1 分（如果棋子现在位于蓝色格子）或失去 1 分（如果棋子现在位于红色格子）。

当某一玩家无法执行操作时游戏结束。此时若两人分数不同，分数多者获胜；否则平局。

两人都为了获得最佳结果而进行游戏，求游戏的结果。

输入格式

输入按以下格式从标准输入给出：

$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}$
$\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，所以平局。

数据范围

• $1 \le H, W \le 2000$
• $A_{i,j}$ 为 + 或 -