CF1658E.Gojou and Matrix Game

Marin feels exhausted after a long day of cosplay, so Gojou invites her to play a game!

Marin and Gojou take turns to place one of their tokens on an $n \times n$ grid with Marin starting first. There are some restrictions and allowances on where to place tokens:

• Apart from the first move, the token placed by a player must be more than Manhattan distance $k$ away from the previous token placed on the matrix. In other words, if a player places a token at $(x_1, y_1)$, then the token placed by the other player in the next move must be in a cell $(x_2, y_2)$ satisfying $|x_2 - x_1| + |y_2 - y_1| \gt k$.
• Apart from the previous restriction, a token can be placed anywhere on the matrix, including cells where tokens were previously placed by any player.

Whenever a player places a token on cell $(x, y)$, that player gets $v_{x,\ y}$ points. All values of $v$ on the grid are distinct. You still get points from a cell even if tokens were already placed onto the cell. The game finishes when each player makes $10^{100}$ moves.

Marin and Gojou will play $n^2$ games. For each cell of the grid, there will be exactly one game where Marin places a token on that cell on her first move. Please answer for each game, if Marin and Gojou play optimally (after Marin's first move), who will have more points at the end? Or will the game end in a draw (both players have the same points at the end)?

Marin 经过一整天的 Cosplay 后感到筋疲力尽，于是 Gojou 邀请她一起玩游戏！

Marin 和 Gojou 轮流在一个 $n \times n$ 的网格上放置各自的棋子，Marin 先手。棋子的放置需满足以下限制与允许条件：

• 除第一步外，当前玩家所放置的棋子必须与上一次（即对方）所放置的棋子之间的曼哈顿距离严格大于 $k$。换言之，若某玩家将棋子置于 $(x_1, y_1)$，则另一玩家在下一步所放置的棋子必须位于满足 $|x_2 - x_1| + |y_2 - y_1| \gt k$ 的格子 $(x_2, y_2)$ 上。
• 除上述限制外，棋子可放置于网格中任意位置，包括已被任一玩家放置过棋子的格子。

每当一名玩家在格子 $(x, y)$ 上放置一枚棋子，该玩家即获得 $v_{x,\ y}$ 分。网格中所有 $v$ 值互不相同。即使某个格子上已存在棋子，再次在该格子上放置棋子仍可获得对应分数。游戏持续进行，直至双方各自完成 $10^{100}$ 步。

Marin 和 Gojou 将共进行 $n^2$ 局游戏。对于网格中的每个格子，恰好有一局游戏中 Marin 的第一步是将棋子放在该格子上。请对每一局游戏回答：若 Marin 和 Gojou 在 Marin 第一步之后均采取最优策略，最终谁的总分更高？还是游戏以平局结束（双方最终得分相等）？

The first line contains two integers $n$, $k$ ($3 \le n \le 2000$, $1 \leq k \leq n - 2$). Note that under these constraints it is always possible to make a move.

The following $n$ lines contains $n$ integers each. The $j$-th integer in the $i$-th line is $v_{i,j}$ ($1 \le v_{i,j} \le n^2$). All elements in $v$ are distinct.

第一行包含两个整数 $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$ 中的所有元素互不相同。

You should print $n$ lines. In the $i$-th line, print $n$ characters, where the $j$-th character is the result of the game in which Marin places her first token in the cell $(i, j)$. Print 'M' if Marin wins, 'G' if Gojou wins, and 'D' if the game ends in a draw. Do not print spaces between the characters in one line.

你需要输出 $n$ 行。在第 $i$ 行中，输出 $n$ 个字符，其中第 $j$ 个字符表示 Marin 将她的第一个棋子放置在格子 $(i, j)$ 时该对局的结果：若 Marin 获胜，输出 'M'；若 Gojou 获胜，输出 'G'；若平局，输出 'D'。同一行中的字符之间不要添加空格。