Problem Description

This problem is translated from PA 2018 Round 5 Gra.

It is the weekend now. You can finally relax and play your favorite strategy game. The goal of the game is to collect all the coins on the map and bring them back to the base. The rules are as follows:

• The map is an $n\times n$ grid. Rows are numbered from $0$ to $n-1$ from top to bottom, and columns are numbered from $0$ to $n-1$ from left to right. We use $(r,c)$ to denote the cell in row $r$ and column $c$. Two cells are adjacent if and only if they share a side.
• Your base is located at cell $(0,0)$ in the top-left corner. You can recruit new characters there, and you must bring collected coins back there. In the remaining $n^2-1$ cells, each cell initially contains either some number of coins or some number of stones.
• There are two types of characters that can move on the map: a farmer can collect coins but cannot enter a cell containing stones, while a tank can clear stones and can enter any type of cell.
• The game proceeds in rounds. In each round, each character may move at most once, to a cell adjacent to its current cell. Two characters cannot be in the same cell at the same time. All moves are instantaneous (movement takes zero time).
• If at the end of a round a farmer is on a cell with coins, it takes $10$ coins and puts them into its backpack. If the cell has fewer than $10$ coins, it takes all of them. The farmer’s backpack has unlimited capacity. However, a farmer cannot enter a cell where the number of stones is not $0$. If at the end of a round the farmer returns to the base, it unloads all coins in its backpack into the base.
• If at the end of a round a tank is on a cell with stones, it clears $10$ stones from that cell (or all of them if there are fewer than $10$).
• Initially, the base contains $200$ coins. Buying any character (farmer or tank) costs $100$ coins (before buying, the base must have at least that many coins). After buying, the character appears immediately, so a newly bought character can also move in the same round.

Your task is: for each input map (that is, for each test case), find a sequence of commands such that after playing according to this sequence, all coins on the map have been brought back to the base (and may have been partially or completely spent). In other words, in the final state, no cell contains any coins, and no farmer’s backpack contains any coins. The commands are shown in the table below:

Your program will be tested on testdata prepared by the organizers. Each testdata set consists of a number of maps (test cases). Each testdata set has a limit $k$ (see the “Constraints and Limits” section). This is a limit on the average number of rounds per testdata set. In other words, if there are $T$ maps in the testdata set, your program must finish all games within at most $T\cdot k$ rounds in total. We define the number of rounds for one test case as the number of times the command $\texttt{=}$ is used plus $1$.

Invalid commands, exceeding the round limit, or failing to achieve the goal will all be judged as Wrong Answer.

Input Format

The first line contains two integers $T,k$, denoting the number of test cases and the average round limit. In all testdata except the sample, $T=10$.

For each testdata set, the first line contains a positive integer $n$. In all testdata except the sample, $n=20$.

Then follow $n$ lines, each with $n$ integers. $0$ denotes the base (which is always in the top-left corner). A positive number $a$ means this cell contains $a$ coins, and a negative number $a$ means this cell contains $|a|$ stones.

The map is generated as follows: for each testdata set, the organizers choose a constant $p\ (0\le p<1)$, which is the probability that a cell contains stones. For each cell except the base, an integer $x$ is chosen uniformly at random from $0$ to $9$, and then $a=2^x$ is assigned to this cell. After that, with probability $p$, this value is multiplied by $-1$.

Output Format

For each test case, output a sequence of commands, one command per line. You may output at most $2\ 000\ 000$ commands.

2 12
3
0 -8 -512
-16 -1 -128
8 -2 -512
3
0 64 -1
64 -1 -1
1 -1 -1

R TANK
M 0 0 1 0
=
=
M 1 0 1 1
R FARMER
M 0 0 1 0
=
M 1 0 2 0
=
M 2 0 1 0
=
M 1 0 0 0
=
===
R FARMER
M 0 0 0 1
R FARMER
M 0 0 1 0
=
=
=
=
M 0 1 0 0
=
M 0 0 0 1
=
=
M 1 0 2 0
=
M 2 0 1 0
=
M 1 0 0 0
=
M 0 0 1 0
=
R FARMER
M 1 0 2 0
M 0 0 1 0
M 0 1 0 0
=
===

Hint

Sample 1 Explanation

For the first test case, we first buy a tank and immediately move it from $(0,0)$ to $(1,0)$, so that all stones are cleared in two rounds. Then we move the tank to $(1,1)$, buy a farmer at the base, and send it to $(2,0)$ to collect coins. After all coins are collected, we let the farmer return the coins and empty its backpack. We could buy a farmer in the first round, but it would have to wait until the tank clears the stones before it can move.

The second test case shows a solution that is not optimal but is correct. Note that a farmer can leave a cell without collecting all the coins on it. Recruiting the first two characters will spend all initial coins ($200$), so we can only buy the third character after the farmer brings $100$ coins back to the base.

The first test case uses $7$ rounds, and the second test case uses $13$ rounds. The average is $10$ rounds, which does not exceed the given limit $k$.

Constraints

This problem uses bundled tests.

There are ten subtasks, and each subtask contains $2$ to $5$ testdata sets. The exact values of $p$ and $k$ are given in the table below:

Please note that the sample and the testdata differ slightly in map size and in the number of test cases.

Translated by ChatGPT 5