Chain Reaction Building Game Simulation

The game is played on an n × m grid. Initially, all cells are empty. The game is provided with a building sequence which determines the level of building units to be placed during BUILD operations. A building unit has one of nine levels: \(L_1, L_2, L_3, \ldots, L_9\). The score for placing or generating a building of level \(L_i\) is given by the following table:

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

The game features a chain reaction mechanism. After placing a building unit (either by a BUILD operation or by the automatic transformation of a star), a reaction is checked at that cell. If the connected component (cells connected via up/down/left/right with the same level as the placed unit) has size \(\ge 3\) and the level is less than 9, then the entire connected component is merged into a single building of the next level. The merge is performed at the position where the building was just placed, and all other cells in the connected component become empty. Each merging (i.e. reaction) scores the points corresponding to the newly generated building. Reactions may cascade.

Additionally, there are two types of items available which can be used at any time:

• Star: Can be placed on an empty cell. When a star is placed, it automatically transforms into the highest-level building (from \(L_9\) down to \(L_1\)) such that if placed there, the connected component (including this new cell and any adjacent cells with the same level already on board) would have size at least 3, causing a reaction. If no level can trigger a reaction, the star becomes \(L_1\). The score is added based on the level it finally turns into (and potential subsequent reactions).
• Bomb: Can be used on a cell that already has a building. It removes the building, returning the cell to empty, and subtracts half of that building's score from the total (note that the half value is always an integer based on the table above).

You are given the grid dimensions, the number of stars \(p\) and bombs \(q\) available, and a sequence of \(t\) operations. There are three types of operations:

• BUILD r c: Place the next building from the building sequence at the blank cell located at row \(r\) and column \(c\). Rows and columns are 1-indexed. After placement, add the corresponding building score and process chain reactions if applicable.
• STAR r c: Use a star item (if available) on the empty cell \((r, c)\). Determine the highest level \(L\) (from \(L_9\) to \(L_1\)) such that if the building of level \(L\) is placed there, the connected component (including adjacent same-level cells) would have size at least 3. If none qualifies, the star becomes \(L_1\). Then add the score for that building and process any reactions.
• BOMB r c: Use a bomb item (if available) on the cell \((r, c)\) containing a building. Remove the building and subtract half of that building's score.

The goal is to simulate the game and calculate the final score after processing all \(t\) operations.

Note: When a reaction occurs at a cell, repeatedly check for further reactions after each merge.

inputFormat

The first line contains five integers \(n, m, p, q, t\) where:

• \(n, m\): the dimensions of the grid (rows and columns).
• \(p\): the initial number of star items available.
• \(q\): the initial number of bomb items available.
• \(t\): the total number of operations.

The second line is a string representing the building sequence. Its length equals the number of BUILD operations in the next \(t\) lines; each character is a digit between 1 and 9 representing the level \(L_i\) to be built.

Each of the next \(t\) lines contains an operation in one of the following formats:

• BUILD r c
• STAR r c
• BOMB r c

It is guaranteed that for a BUILD or STAR operation the cell \((r, c)\) is empty, and for a BOMB operation the cell \((r, c)\) contains a building. Rows and columns are 1-indexed.

outputFormat

Output a single integer: the final score after processing all operations.

sample

3 3 0 0 1
1
BUILD 2 2

4

</p>