P5570 [NOI2012] Triple Town

Student Xiao Xi recently became interested in the iOS game *Triple Town*. After playing, Xiao Xi also started thinking about how to get a higher score in this game.

As shown in the figure below, the game is played on an $n \times m$ grid map. The game provides a **building sequence**. The player chooses an empty cell each time and places the corresponding building unit in order. Buildings have nine different levels. From low to high they are `Grass`, `Bush`, `Tree`, `Hut`, etc. (for convenience, we call them $L_1, L_2, L_3, \ldots , L_9$).  After the player builds a unit on an empty cell, it may trigger a reaction. A reaction happens if: **starting from this cell, the size of the connected component formed by cells with the same building level as this unit is at least $3$**. Then this connected component will be merged into one building of the next level. The new building is placed at the position of the last built unit, and all other cells in the component become empty. Here, a connected component means a set of positions that are directly or indirectly adjacent. Also note that **$L_9$ is the highest level, so connected components of multiple $L_9$ will not merge**. For example, in the figure below, after building the middle $L_1$, the $L_1$ connected to it are merged into one $L_2$.  Note that during merging, chain reactions may occur, as shown below.  The game score depends on the units the player builds and the units generated by reactions. Whenever a building unit is placed or generated by a reaction, the corresponding score is added. The score table for different building levels is as follows: |Building|$L_1$|$L_2$|$L_3$|$L_4$|$L_5$|$L_6$|$L_7$|$L_8$|$L_9$| |:----:|:-----:|:-----:|:-----:|:-----:|:-----:|:-----:|:-----:|:-----:|:-----:| |Score|$4$|$20$|$100$|$500$|$1500$|$5000$|$20000$|$100000$|$500000$| Using the two game processes above as examples: in Figure 2, first an $L_1$ is built, gaining $4$ points. Then the $L_1$ reacts and generates an $L_2$, gaining another $20$ points. The total is $24$. In Figure 3, this move scores $4+20+100+500=624$ points. To reduce the difficulty, the game also provides two items: “star” and “bomb”. At the start of the game, the player is given $p$ stars and $q$ bombs, and can use them at any time. Their functions are: - “Star” item: It can be placed on an empty cell. When a star is placed, it automatically becomes the **highest-level building that can trigger a reaction**. If no reaction can be triggered at that position, the star becomes $L_1$. For example, placing a star at the very center in Figure 3, the star automatically becomes $L_3$. The score of the star is calculated according to the building level it becomes. - “Bomb” item: A bomb can be placed on a cell that already has a building. It destroys the building and turns that cell back into empty. When using a bomb, half of the destroyed building’s score is deducted (i.e. the score added is negative). During the game, the player must place buildings in the given order, but may interleave the use of the two items at any time. The goal is to achieve the highest possible score through proper operations.

**This is an output-only problem.** For each test, the first line of the input file contains two integers $n$, $m$, indicating that the map has $n$ rows and $m$ columns. The next line contains two integers $p$, $q$, indicating the number of star items and bomb items. The next $n$ lines contain the initial $n \times m$ map. The character `.` means an empty cell, and digits $1\sim 9$ represent buildings of the corresponding levels. The next line contains a number $k$, indicating the length of the building sequence. The last line contains $k$ space-separated integers between $1\sim 9$, indicating the content of the building sequence.

For the given $10$ input files `tritown1.in` ~ `tritown10.in`, you need to submit your output files `tritown1.out` ~ `tritown10.out` respectively. Each output file contains the player’s game commands. There are $4$ types of commands: |Command|Meaning| |:--:|:----------:| |`PUT x y`|Place the next unit in the building sequence into the empty cell at row $x$, column $y$.| |`STAR x y`|Place a star item into the empty cell at row $x$, column $y$.| |`BOMBER x y`|Place a bomb at row $x$, column $y$. This cell must be non-empty.| |`END`|End the game and settle the current score.| The output must end with the `END` command. The player may end the game at any time.

#### Sample Explanation This sample corresponds to the figure below:  The first move scores $4+20+100=124$. The second move scores $100$. The third move scores $100+500=600$. The total score is $124+100+600=824$. #### Scoring For each test, we provide $9$ scoring parameters $a_{10}, a_9, \ldots, a_2$, one per line in this order, in the additional files `tritown1.ans` ~ `tritown10.ans`. If your output is invalid, you get $0$ points. Otherwise, let your game score be $w_{user}$. Your score is given by the table below: |Score|Condition|Score|Condition| |:----:|:------:|:----:|:------:| |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$| If multiple conditions are satisfied, take the highest score among them. #### Additional Files The checker needs to be compiled before use. Please go to [Github](https://github.com/MikeMirzayanov/testlib) to download the latest source code of testlib.h. Translated by ChatGPT 5