Марин измоталась после долгого дня косплея, поэтому Годзё приглашает ее сыграть в игру!
Марин и Годзё по очереди кладут одну из своих фишек на таблицу размером \(n \times n\), при этом Марин ходит первой. Существуют некоторые ограничения на размещение фишек:
- За исключением первого хода фишка, размещенная игроком, должна находиться на манхэттенском расстоянии более чем \(k\) от последней размещенной фишки. Другими словами, если игрок кладет фишку в \((x_1, y_1)\), то фишка, помещенная на следующем ходу, должна находиться в ячейке \((x_2, y_2)\), удовлетворяющей \(|x_2 - x_1| + |y_2 - y_1| > k\).
- Помимо предыдущего ограничения, фишка может быть размещена в любом месте матрицы, включая ячейки, где уже были размещены фишки любого игрока.
Каждый раз, когда какой-либо игрок кладет фишку в ячейку \((x, y)\), этот игрок получает \(v_{x,\ y}\) очков. Все значения \(v\) в таблице различны. Очки за ячейку даются даже в случае, если какие-то фишки уже находятся в этой ячейке. Игра заканчивается, когда каждый игрок сделает \(10^{100}\) ходов.
Марин и Годзё сыграют \(n^2\) партий. Для каждой ячейки таблицы будет ровно одна партия, в которой первым ходом Марин размещает фишку в этой ячейке. Для каждой такой партии определите, у кого в итоге будет больше очков при оптимальной игре Марин и Годзё (после первого хода Марин)? Или партия закончится вничью?
Выходные данные
Выведите \(n\) строк. \(i\)-я строка должна содержать \(n\) символов, где \(j\)-й символ является результатом партии, в которой Марин начинает с ячейки \((i, j)\). Выведите 'M' в случае победы Марин, 'G' — в случае победы Годзё и 'D' — в случае равного количества очков. Не выводите пробелы между символами в одной строке.