经过一整天的cosplay,玛琳感到疲惫不堪,所以五条邀请她玩游戏!
Marin 和 Gojou 轮流将他们的一个代币放在 $$$n \times n$$$ 网格上,Marin 首先开始。对于放置代币的位置有一些限制和允许:
- 除了第一步之外,玩家放置的令牌与矩阵上放置的前一个令牌的距离必须大于曼哈顿距离$$$k$$$。换句话说,如果玩家在 $$$(x_1, y_1)$$$ 处放置了令牌,则另一玩家在下一步中放置的令牌必须位于满足 $$$|x_2 - x_1| 的单元格 $$$(x_2, y_2)$$$ 中。 + |y_2 - y_1| > k$$$。
- 除了之前的限制之外,令牌可以放置在矩阵上的任何位置,包括任何玩家之前放置令牌的单元格。
每当玩家在单元格 $$$(x, y)$$$ 上放置令牌时,该玩家就会获得 $$$v_{x,\ y}$$$ 点。网格上 $$$v$$$ 的所有值都是不同的。即使代币已经放置在单元格上,您仍然可以从单元格中获得积分。当每个玩家移动 $$$10^{100}$$$ 时,游戏结束。
Marin 和 Gojou 将玩 $$$n^2$$$ 游戏。对于网格的每个单元格,都会有一场游戏,马林在第一次移动时在该单元格上放置一个标记。请回答每场比赛,如果马林和五条发挥最佳(在马林第一步之后),最后谁会获得更多分数?或者比赛会以平局结束(最终双方得分相同)?
输入
第一行包含两个整数 $$$n$$$、$$$k$$$ ($$$3 \le n \le 2000$$$、$$$1 \leq k \leq n - 2$$$)。请注意,在这些限制下,总是可以采取行动。
以下 $$$n$$$ 行每行包含 $$$n$$$ 个整数。第 $$$i$$$ 行中的第 $$$j$$$ 整数为 $$$v_{i,j}$$$ ($$$1 \le v_{i,j} \le n^2$$$)。 $$$v$$$ 中的所有元素都是不同的。
输出
您应该打印 $$$n$$$ 行。在第 $$$i$$$ 行中,打印 $$$n$$$ 个字符,其中第 $$$j$$$ 个字符是 Marin 将她的第一个标记放入单元格 $$$(i, j)$$$ 中的游戏结果。如果 Marin 获胜则打印“M”,如果 Gojou 获胜则打印“G”,如果比赛以平局结束则打印“D”。不要在一行中的字符之间打印空格。
示例
输入 #1
3 1 1 2 4 6 8 3 9 5 7
输出 #1
GGG MGG MGG