题目描述

题目译自 PA 2018 Runda 5 Gra

现在已经是周末了！你终于可以放松一下，玩你最喜欢的策略游戏了。这个游戏的目标是收集地图上的所有金币并将它们运回基地，规则如下：

• 地图由一个 $n\times n$ 的网格构成。行从上到下编号为 $0$ 到 $n-1$，列从左到右编号为 $0$ 到 $n-1$。我们用 $(r,c)$ 表示第 $r$ 行第 $c$ 列的单元格。两单元格相邻当且仅当它们共享同一条边。
• 你的基地位于单元格 $(0,0)$，它位于左上角。你可以在那里招募新的角色，并且你必须把收集到的金币带到那里。剩下的 $n^2-1$ 个格子中初始要么有一定数量的金币，要么有一定数量的石头。
• 游戏中有两种可以在地图上移动的角色：农民可以收集金币，但不可以进入有石头的单元格，坦克可以清除石头，并且可以进入任何种类的单元格。
• 游戏分轮次进行。每轮每个角色可以至多移动一次，移动到与它所在的单元格相邻的单元格中。两个角色不能在同一时间处于同一单元格中。所有移动都是瞬时的（移动花费的时间为零）。
• 如果在一轮结束时，农民位于有金币的单元格中，他就会拿走 $10$ 枚金币并放到自己的背包里。如果单元格中的金币少于 $10$ 枚，他就会全部拿走。农民的背包容量无限。但农民无法进入石头量不为 $0$ 的单元格中。如果在一轮结束时农民回到了基地，他就会把背包里所有的金币放回基地。
• 如果在一轮结束时，坦克位于有石头的单元格中，它就会清除单元格中的 $10$ 个石头（如果少于 $10$ 个则清除全部）。
• 最初基地中有 $200$ 枚金币。每买一种角色——农民或者坦克——都要花费 $100$ 金币（买之前在基地中必须至少有这么多金币），买后角色即时出现。所以新角色可以在同一轮移动。

你的任务是，对于每一个输入给定的地图（也就是对于每个测试点），找到一个操作序列，使得按这个操作序列进行游戏后，所有地图上的金币都被运回了基地（并且可能部分或全部花掉了）。换句话说，结束后的地图上，任何单元格中都没有金币，任何农民的背包里也没有金币。命令如下表所示：

你的程序会使用组织者准备的测试数据进行测试，每组测试数据由一定数量的地图——也就是测试点组成。每组测试数据都有一个限制 $k$（请参考「数据范围及限制」一节）。这是对于每组数据平均轮数的限制。换句话说，如果测试数据中有 $T$ 张地图，你的程序必须在最多 $T\cdot k$ 轮结束所有游戏。我们定义每个测试点的轮数为使用命令 $\texttt{=}$ 的次数加 $1$。

错误的命令，超出轮数限制或没有达成目标，均会被判为 Wrong Answer。

输入格式

第一行包含两个整数 $T,k$，表示测试点个数和平均轮数限制。除了样例外所有测试数据都有 $T=10$。

对于每组数据，第一行一个正整数 $n$。除了样例外所有测试数据都有 $n=20$。

接下来 $n$ 行，每行 $n$ 个整数。$0$ 表示基地（一定位于左上角）。正数 $a$ 意味着这个单元格有 $a$ 枚金币，负数 $a$ 意味着这个单元格有 $|a|$ 个石头。

地图按如下方式生成：对于每组测试数据，组织者会选择一个常数 $p\ (0\le p<1)$，表示单元格中有石头的概率。对于每个除基地以外的单元格，随机选择一个在 $0$ 到 $9$ 范围内的整数 $x$，然后将 $a=2^x$ 赋给这个单元格。在此之后，以 $p$ 的概率给这个值乘以 $-1$。

输出格式

对于每组测试点，输出操作序列。一条命令输出一行。最多输出 $2\ 000\ 000$ 条命令。

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
=
===

提示

样例 1 解释

对于第一个测试点，我们首先买了一辆坦克，并立即从 $(0,0)$ 移动到 $(1,0)$，这样在两轮中清除掉了所有石头。然后我们将坦克移动到 $(1,1)$，在基地中买一个农民，并将其送到 $(2,0)$ 收集金币。当金币收集完后，我们让农民返回金币并清空背包。我们可以在第一轮就购买一个农民，但他需要一直等到坦克清除石头后才能移动。

第二个测试点展示了一种不是最优但正确的答案。注意农民可以在不收集全部金币的情况下离开这个单元格。招募前两个角色就会花掉所有初始金币（$200$），所以我们只能在农民向基地运回 $100$ 金币后买第三个角色。

第一个测试点中使用了 $7$ 轮，第二个测试点使用了 $13$ 轮。平均是 $10$ 轮，没有超过给定 $k$ 的限制。

数据范围

本题采用捆绑测试

共有十个子任务，每个子任务包含 $2$ 到 $5$ 个测试数据。确切的 $p$ 值和 $k$ 值如下表所示：

请注意样例和测试数据在地图大小和测试点个数上稍有不同。