题目描述
我们有一个 $H$ 行 $W$ 列的网格,每个网格都是蓝色或红色的。如果 $A_{i, j}$ 是 `+`,那么位于第 $i$ 行第 $j$ 列的方格是蓝色的;如果 $A_{i, j}$ 是 `-`,那么位于第 $i$ 行第 $j$ 列的方格是红色的。
这个网格上有一个棋子,最初被放在左上角的位置。高桥和青木将用这颗棋子下一盘棋。
一开始,两位棋手均为 $0$ 分。他们将交替进行以下操作,高桥先手:
- 将棋子向右或向下移动一格。不允许将棋子移到网格外。然后,如果棋子现在在蓝色方格上,则(当前移动棋子的)棋手会得到一分,如果棋子现在在红色方格上,则会失去一分。
当其中一名玩家无法进行操作时,游戏结束。然后,如果双方点数不同,则点数多的一方获胜;否则,算作平局。
如果双方都希望获得最佳结果,试判断最终的游戏结果。
输入格式
输入内容由标准输入法提供,格式如下:
>$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 \le H, W \le 2000$
- $A_{i, j}$ 是 `+` 或 `-` 的其中一种