P5570 [NOI2012] 三重镇

小西同学最近喜欢上了 iOS 游戏《三重镇 Triple Town》。游戏之余，小西也在思考如何才能在这个游戏中获得更高的分数。

如下图所示，游戏在一个 $n \times m$ 的地图中进行。游戏给定一个**建造序列**，玩家按照此建造序列依次选择空白位置建造相应的建筑单位。建筑有九个不同的等级，由低到高分别为 `Grass`, `Bush`, `Tree`, `Hut` 等（为了方便描述，我们称之为 $L_1, L_2, L_3, \ldots , L_9$）。  当玩家在一个空白位置建造单位之后，有可能引起反应。反应的构成条件是：**从这个格子出发，与该建筑单位等级相同的格子所构成的连通块大小大于等于 $3$**， 则这个连通块将被合并为一个下一等级的建筑，此建筑的位置为最后建造的建筑单位位置，连通块中其他位置将变回空格。这里的连通块是指直接或者间接相邻的位置集合。 另外需要注意的是，**$L_9$ 为建筑的最高等级，所以多个 $L_9$ 的连通块并不会合并**。例如在下图中，当建造了中间的 $L_1$ 之后，与该位置相连的 $L_1$就被合并成了一个 $L_2$。  注意，在合并的过程中，可能会引起连环反应，如下图所示。  游戏的得分取决于玩家建造和反应生成的单位，建造或者反应生成建筑单位就可以获得相应的分数。不同等级建筑的得分表如下： |建筑|$L_1$|$L_2$|$L_3$|$L_4$|$L_5$|$L_6$|$L_7$|$L_8$|$L_9$| |:----:|:-----:|:-----:|:-----:|:-----:|:-----:|:-----:|:-----:|:-----:|:-----:| |得分|$4$|$20$|$100$|$500$|$1500$|$5000$|$20000$|$100000$|$500000$| 以刚才的两个游戏过程为例。图 2 中，首先建造了 $L_1$, 将得到 $4$ 分，随后， $L_1$ 进行了反应生成了 $L_2$, 此时再得到 $20$ 分。总共得分为 $24$。而在图 3 中，这一步操作得分为 $4+20+100+500=624$ 分。 为了降低游戏的难度，游戏中还设有两种道具，分别为“星星”和“炸弹”。在游戏开始时，玩家被给定 $p$ 个星星道具和 $q$ 个炸弹道具，玩家可以在任意时刻使用。两者功能如下： - “星星”道具：可以放置在一个空格位置。当星星被放置时，星星会自动变为**能引起反应的最高等级建筑**。当在该位置不能引起任何反应时，星星变为 $L_1$。例如，在图 3 正中间位置放置星星，星星自动变为 $L_3$。星星的得分按照变化后的建筑计算得分。 - “炸弹”道具：炸弹道具可以放在在一个有建筑的位置上，作用为炸掉这个建筑并将该位置恢复为空格。当使用炸弹时，得分将扣除被炸掉的建筑的一半分数（即，得分为负数）。 在游戏的进行过程中，玩家必须按照给定的顺序进行建造，但可以随时穿插使用两种道具。游戏的目标是，通过合理的操作，取得最高的分数。

**本题是一道提交答案题。** 对于每个数据，输入文件中第一行为两个整数 $n$，$m$, 表示地图一共包含 $n$ 行 $m$ 列。 接下来一行包含两个整数 $p$，$q$，分别表示道具星星和道具炸弹的数目。 接下来 $n$ 行包含一个 $n \times m$ 的初始地图。其中字符 `.` 表示空地，数字 $1\sim 9$ 分别表示相应等级的建筑。 再接下来一行包含一个数字 $k$，表示建造序列的长度。 最后一行包含 $k$ 个空格隔开的 $1\sim 9$ 之间的数字，表示建造序列的内容。

针对给定的 $10$ 个输入文件 `tritown1.in` ~ `tritown10.in`，你需要分别提交你的输出文件 `tritown1.out` ~ `tritown10.out`。 输出文件包含玩家进行游戏的指令，共 $4$ 种指令： |指令|含义| |:--:|:----------:| |`PUT x y`|将建造序列中的下一个单位放置到第 $x$ 行第 $y$ 列的空格中。 |`STAR x y`|放置星星道具到第$x$行第$y$列的空格中。| |`BOMBER x y`|在第 $x$ 行第 $y$ 列放置炸弹，此位置必须非空。| |`END`|游戏结束，结算当前得分。| 输出必须以 `END` 指令结尾，玩家可以在任意时刻结束游戏。

#### 样例解释 本样例对应下图：  第一步得分为 $4+20+100=124$； 第二步得分为 $100$； 第三步得分为 $100+500=600$； 游戏总得分 $124+100+600=824$ 分。 #### 评分标准 对于每组数据，我们设置了 $9$ 个评分参数 $a_{10}, a_9, …, a_2$，它们按此顺序每行一个放置在附加文件中的 `tritown1.ans` ~ `tritown10.ans` 内。如果选手的输出不合法，则得零分。否则，设在你的方案中，游戏得分为 $w_{user}$，你的分数将会由下表给出： |得分|条件|得分|条件| |:----:|:------:|:----:|:------:| |10|$w_{user}\geq a_{10}$|5|$w_{user}\geq a_5$| |9|$w_{user}\geq a_9$|4|$w_{user}\geq a_4$| |8|$w_{user}\geq a_8$|3|$w_{user}\geq a_3$| |7|$w_{user}\geq a_7$|2|$w_{user}\geq a_2$| |6|$w_{user}\geq a_6$|1|$w_{user}>0$| 如果有多项满足，则取满足条件中的最高得分。 #### 附加文件 checker 需要自行编译后使用。 请前往 [Github](https://github.com/MikeMirzayanov/testlib) 下载 testlib.h 的最新源代码。