题目背景

小西同学最近喜欢上了 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 指令结尾，玩家可以在任意时刻结束游戏。

2 3
1 1
..1
221
2
1 3

PUT 1 2
PUT 1 1
STAR 2 1
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 下载 testlib.h 的最新源代码。