311332: CF1970F3. Playing Quidditch (Hard)

F3. Playing Quidditch (Hard)time limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

This afternoon, you decided to enjoy the first days of Spring by taking a walk outside. As you come near the Quidditch field, you hear screams. Once again, there is a conflict about the score: the two teams are convinced that they won the game! To prevent this problem from happening one more time, you decide to get involved in the refereeing of the matches.

Now, you will stay in the stadium to watch the game and count the score. At the end of the game, you will decide the winner.

Today, two teams are competing: the red Gryffindor (R) and the blue Ravenclaw (B) team. Each team is composed of $P$ players ($1 \leq P \leq 10$).

The field is a rectangle of $N$ lines and $M$ columns ($3 \leq N, M \leq 99$, $N$ and $M$ are odd). All the positions are integers, and several entities are allowed to be at the same position in the field. At the beginning of the game, the field contains goals for the two teams (each team can own between one and five goals), the players, and exactly one Quaffle. In this version of the problem, one Bludger and a Golden Snitch can be present.

A game is composed of $T$ steps ($0 \leq T \leq 10000$). At each step, one entity on the field (a player or a ball) performs one action. All entities can move. A player can also catch a ball or throw the Quaffle that it is carrying. To catch a ball, a player must be located on the same cell as it. The Quaffle does not perform any action while it is being carried; it only follows the movements of the player. If a player carrying the Quaffle decides to throw it, the Quaffle is simply put at the current position of the player. If a player is on the same cell as a Bludger (either after a movement from the player or the Bludger), the player is eliminated. If the player is eliminated while it is carrying the Quaffle, the Quaffle remains on the cell containing both the player and the Bludger after the move. It is guaranteed that this never occurs while the player is in a cell containing a goal.

To win a point, a player must leave the Quaffle at a goal of the other team. When it does, the team of the player wins one point, and the Quaffle instantly moves to the middle of the field (the cell at the $(M+1)/2$-th column of the $(N+1)/2$-th line of the field, starting from 1). There is no goal in the middle of the field. If a player puts the ball in its own goal, the other team wins the point. If a player catches the Golden Snitch, their team wins 10 points and the game is over.

Input

On the first line, the integers $N$ and $M$.

The description of the field follows: $N$ lines of $M$ pairs of characters separated by spaces. Each pair of characters represents a position on the field. It can be either:

• .. to represent an empty cell
• R0, ..., R9, B0, ..., B9 to represent a player. The first character is the team of the player, and the second is the number of the player in the team. Each pair of characters is unique, but it is not guaranteed that all the pairs appear in the grid.
• RG or BG to represent a goal. The blue team tries to put the ball in a red goal (RG) while the red team tries to put the ball in a blue goal (BG).
• .Q to represent the Quaffle, which is the ball that the players use to score goals.
• .B to represent the Bludger.
• .S to represent the Golden Snitch.

The next line contains $T$, the number of steps that compose the game. $T$ lines follow, each describing one action. It contains several pieces of information separated by a space. First, a pair of characters representing the entity that must perform the action. Second, the description of the action:

• U, D, L, R indicate that the entity moves on the grid. It can move to the top of the grid (U), to the bottom (D), to the left (L), or to the right (R). Each entity moves by only one cell at a time.
• C indicates that the player catches the ball (only a player can catch a ball). Then, there is a space followed by a pair of characters: the description of the ball caught by the player. This information is needed since several balls can be in the same cell.
• T indicates that the player throws the Quaffle that it is carrying.

All the actions performed by the entities are guaranteed to be valid: the players stay in the field, don't catch a ball if they are not in the same cell, don't release the Quaffle if they are not carrying it, ...

Output

You must output the description of the main events of the game, one event per line. More precisely:

• Each time a team scores, you must print t RED GOAL or t BLUE GOAL, depending on the team who scored, where t is the current time (the position of the action in the list of actions, starting from 0). In the case where a player scores in the wrong goal (a red player scores in the red goal, or a blue player scores in the blue goal), you must print the name of the team who wins one point, that is, the other team.
• Each time a player is eliminated, you must print t p ELIMINATED, where t is the current time and p is the player who is eliminated. The format to print the player is the same as in the input.
• If the Golden Snitch is caught, you must print t RED CATCH GOLDEN SNITCH or t BLUE CATCH GOLDEN SNITCH, depending on the team who caught the Golden Snitch, where t is the current time.

The events must be printed in ascending order of t. If several players are eliminated at the same time, the events must be written is alphabetical order: B0, ..., B9, R0, ... R9.

At the end of the game, you must print the final score as: FINAL SCORE: r b, where r is the score of the red team and b is the score of the blue team.

ExamplesInput

3 5
.. .. R0 .. ..
RG .. .Q .. BG
.. .. B0 .. ..
12
R0 D
R0 C .Q
R0 R
R0 T
R0 D
B0 R
B0 U
B0 C .Q
B0 L
B0 L
B0 L
B0 T

Output

11 BLUE GOAL
FINAL SCORE: 0 1

Input

3 5
.. .. R0 .. ..
RG .. .Q .. BG
.. .. B0 .. ..
5
R0 D
R0 C .Q
R0 L
R0 L
R0 T

Output

4 BLUE GOAL
FINAL SCORE: 0 1

Input

5 5
.. .. .. .. ..
.. .. .. .. ..
RG R0 .Q B0 BG
.. .. .. .. ..
.. .. .B .. ..
5
.B L
.B U
.B U
B0 L
B0 L

Output

2 R0 ELIMINATED
4 B0 ELIMINATED
FINAL SCORE: 0 0

Input

5 5
.. R0 .S B0 ..
.. .. .. .. ..
RG .. .Q .. BG
.. .. .. .. ..
.. R1 .B B1 ..
4
.S D
R0 D
R0 R
R0 C .S

Output

3 RED CATCH GOLDEN SNITCH
FINAL SCORE: 10 0

Note

In the first example, the red player takes the Quaffle, move it and throw it. The blue player catches the ball, goes to the red goal and scores.

In the second example, the red player takes the ball and scores in the goal of their own team: the blue team wins a point.

In the third example, the Bludger goes at the position of R0: R0 is eliminated. Then, B0 moves to the position of the Bludger: B0 is eliminated too.

In the fourth example, a red player catches the Golden Snitch. Their team wins 10 points, and the game ends.

You can find one more example in the easy version of the problem

题目大意：你参与了一场魁地奇比赛的裁判工作。比赛中有两个队伍：红色格兰芬多队（R）和蓝色拉文克劳队（B），每个队伍有P名球员（1 ≤ P ≤ 10）。比赛场地是一个N行M列的矩形（3 ≤ N, M ≤ 99，且N和M都是奇数），场地中可能有多个实体占据同一位置。比赛开始时，场地中包括两个队伍的球门（每个队伍有一个到五个球门）、球员和恰好一个金飞贼。比赛由T步组成（0 ≤ T ≤ 10000），每一步中，场上的一个实体（球员或球）执行一个动作。球员可以移动、接球或扔掉手中的金飞贼。球员必须与球在同一单元格上才能接球。如果球员带着金飞贼决定扔掉它，金飞贼就被放在球员当前的单元格上。如果球员与游走球在同一单元格（无论是球员移动还是游走球移动），该球员被淘汰。如果球员在带着金飞贼时被淘汰，金飞贼留在包含球员和游走球的单元格上。球员在包含球门的单元格上被淘汰的情况不会发生。

为了得分，球员必须将金飞贼留在对方队伍的球门中。这时，该球员的队伍得一分，金飞贼立即移动到场地中央。如果球员将球扔进自己的球门，对方队伍得分。如果球员抓住金色飞贼，他们的队伍得10分，比赛结束。

输入格式：第一行是整数N和M。接下来是场地的描述：N行，每行M对由空格分隔的字符，每对字符代表场地的一个位置。字符对可以是以下几种：
- ".." 表示一个空单元格
- "R0", ..., "R9", "B0", ..., "B9" 表示一个球员。第一个字符是球员所在的队伍，第二个字符是球队中的球员编号。每对字符都是唯一的，但不保证所有字符对都出现在网格中。
- "RG" 或 "BG" 表示一个球门。蓝色队伍试图将球扔进红色球门（RG），而红色队伍试图将球扔进蓝色球门（BG）。
- ".Q" 表示金飞贼。
- ".B" 表示游走球。
- ".S" 表示金色飞贼。

下一行是T，表示组成比赛的步数。接下来T行，每行描述一个动作，包含以下信息：
- 一对字符，表示必须执行动作的实体。
- 动作的描述："U", "D", "L", "R" 表示实体在网格上移动；"C" 表示球员接球；"T" 表示球员扔掉手中的金飞贼。

所有实体的动作都是有效的：球员留在场地内，不在同一单元格上不接球，不带金飞贼时不扔球。

输出格式：你必须输出比赛的主要事件，每个事件一行。具体来说：
- 每当有队伍得分时，你必须打印 "t RED GOAL" 或 "t BLUE GOAL"，其中t是当前时间（动作列表中的位置，从0开始）。如果球员得分错误（红色球员在红色球门得分，或蓝色球员在蓝色球门得分），你必须打印赢得一分的队伍，即对方队伍。
- 每当有球员被淘汰时，你必须打印 "t p ELIMINATED"，其中t是当前时间，p是被淘汰的球员。打印球员的格式与输入中的相同。
- 如果金色飞贼被抓住，你必须打印 "t RED CATCH GOLDEN SNITCH" 或 "t BLUE CATCH GOLDEN SNITCH"，取决于哪个队伍抓住了金色飞贼，其中t是当前时间。

事件必须按t的升序打印。如果同一时间有多个球员被淘汰，事件必须按字母顺序打印：B0, ..., B9, R0, ... R9。比赛结束时，你必须打印最终得分，格式为 "FINAL SCORE: r b"，其中r是红色队伍的得分，b是蓝色队伍的得分。题目大意：你参与了一场魁地奇比赛的裁判工作。比赛中有两个队伍：红色格兰芬多队（R）和蓝色拉文克劳队（B），每个队伍有P名球员（1 ≤ P ≤ 10）。比赛场地是一个N行M列的矩形（3 ≤ N, M ≤ 99，且N和M都是奇数），场地中可能有多个实体占据同一位置。比赛开始时，场地中包括两个队伍的球门（每个队伍有一个到五个球门）、球员和恰好一个金飞贼。比赛由T步组成（0 ≤ T ≤ 10000），每一步中，场上的一个实体（球员或球）执行一个动作。球员可以移动、接球或扔掉手中的金飞贼。球员必须与球在同一单元格上才能接球。如果球员带着金飞贼决定扔掉它，金飞贼就被放在球员当前的单元格上。如果球员与游走球在同一单元格（无论是球员移动还是游走球移动），该球员被淘汰。如果球员在带着金飞贼时被淘汰，金飞贼留在包含球员和游走球的单元格上。球员在包含球门的单元格上被淘汰的情况不会发生。 为了得分，球员必须将金飞贼留在对方队伍的球门中。这时，该球员的队伍得一分，金飞贼立即移动到场地中央。如果球员将球扔进自己的球门，对方队伍得分。如果球员抓住金色飞贼，他们的队伍得10分，比赛结束。 输入格式：第一行是整数N和M。接下来是场地的描述：N行，每行M对由空格分隔的字符，每对字符代表场地的一个位置。字符对可以是以下几种： - ".." 表示一个空单元格 - "R0", ..., "R9", "B0", ..., "B9" 表示一个球员。第一个字符是球员所在的队伍，第二个字符是球队中的球员编号。每对字符都是唯一的，但不保证所有字符对都出现在网格中。 - "RG" 或 "BG" 表示一个球门。蓝色队伍试图将球扔进红色球门（RG），而红色队伍试图将球扔进蓝色球门（BG）。 - ".Q" 表示金飞贼。 - ".B" 表示游走球。 - ".S" 表示金色飞贼。 下一行是T，表示组成比赛的步数。接下来T行，每行描述一个动作，包含以下信息： - 一对字符，表示必须执行动作的实体。 - 动作的描述："U", "D", "L", "R" 表示实体在网格上移动；"C" 表示球员接球；"T" 表示球员扔掉手中的金飞贼。 所有实体的动作都是有效的：球员留在场地内，不在同一单元格上不接球，不带金飞贼时不扔球。 输出格式：你必须输出比赛的主要事件，每个事件一行。具体来说： - 每当有队伍得分时，你必须打印 "t RED GOAL" 或 "t BLUE GOAL"，其中t是当前时间（动作列表中的位置，从0开始）。如果球员得分错误（红色球员在红色球门得分，或蓝色球员在蓝色球门得分），你必须打印赢得一分的队伍，即对方队伍。 - 每当有球员被淘汰时，你必须打印 "t p ELIMINATED"，其中t是当前时间，p是被淘汰的球员。打印球员的格式与输入中的相同。 - 如果金色飞贼被抓住，你必须打印 "t RED CATCH GOLDEN SNITCH" 或 "t BLUE CATCH GOLDEN SNITCH"，取决于哪个队伍抓住了金色飞贼，其中t是当前时间。 事件必须按t的升序打印。如果同一时间有多个球员被淘汰，事件必须按字母顺序打印：B0, ..., B9, R0, ... R9。比赛结束时，你必须打印最终得分，格式为 "FINAL SCORE: r b"，其中r是红色队伍的得分，b是蓝色队伍的得分。