五条悟与矩阵游戏

• 时间限制：5 秒
• 内存限制：256 MiB

题目描述

Marin 与 Gojou 轮流在 $n\times n$ 棋盘上放置棋子，Marin 先手。除第一步外，新棋子与上一步棋子的曼哈顿距离必须严格大于 $k$。棋子可以重复放在任何曾经使用过的格子。

在 $(x,y)$ 放置棋子的玩家得到 $v_{x,y}$ 分。所有 $v_{x,y}$ 两两不同。两人各进行 $10^{100}$ 步后游戏结束。

对棋盘上的每个格子，都考虑一局以 Marin 在该格作为第一步的游戏。双方之后均采用最优策略。请判断每局是 Marin 得分更高、Gojou 得分更高，还是平局。

输入格式

第一行包含两个整数 $n,k$。

接下来 $n$ 行，每行 $n$ 个整数，表示矩阵 $v$。

输出格式

输出 $n$ 行，每行 $n$ 个字符。若以该格为第一步时 Marin 获胜，输出 M；若 Gojou 获胜，输出 G；若平局，输出 D。字符之间不加空格。

样例输入

3 1
1 2 4
6 8 3
9 5 7

样例输出

GGG
MGG
MGG

数据范围

对所有数据，$3\le n\le2000$，$1\le k\le n-2$，$1\le v_{i,j}\le n^2$，且所有分值两两不同。Hydro 包采用 5 秒时限档位。