Codeforces Round 779 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

data structures

dp

games

hashing

implementation

math

number theory

sortings

*2500

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Gojou and Matrix Game

time limit per test

4 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputMarin 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| > 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)?

Input

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.

Output

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.

Example

Input

3 1 1 2 4 6 8 3 9 5 7

Output

GGG MGG MGG

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/23/2024 21:50:51 (j1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|