311330: CF1970F1. Playing Quidditch (Easy)

F1. Playing Quidditch (Easy)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. Other types of balls will be available in the harder versions of the problem.

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.

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.

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.

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 in the next versions of the problem, several balls may 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.

The events must be printed in ascending order of t.

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

5 5
.. R1 .. B1 ..
RG .. .. .. BG
RG R0 .Q B0 BG
RG .. .. .. BG
.. R2 .. B2 ..
13
B2 U
B2 U
B2 L
B2 C .Q
B2 L
B2 L
B2 T
R0 R
R0 C .Q
R0 D
R0 R
R0 R
R0 T

Output

6 BLUE GOAL
12 RED GOAL
FINAL SCORE: 1 1

Input

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

Note

In the first example, a blue player goes to the middle of the grid, at the position of the Quaffle. He takes it, goes to the goal of the red team, and lets the ball there. He scores! The ball gets back to the middle of the field, a red player takes it and scores too.

In the second 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 third example, the red player takes the ball and scores in the goal of their own team: the blue team wins a point.

题目大意：模拟魁地奇比赛得分过程。比赛在一个N行M列的矩形场地上进行，场地可能包含球员、球门和魁地奇球（Quaffle）。比赛由T个步骤组成，每个步骤中，场上的一个实体（球员或球）执行一个动作。球员可以移动、接球或扔球。球员带着魁地奇球移动，当球员将球扔在对方球门中时，己方得一分，球会回到场地中央。如果球员将球扔在自己球门中，对方得一分。需要记录比赛过程中的得分情况，并在比赛结束时输出最终得分。

输入数据格式：
- 第一行：整数N和M，表示场地的大小。
- 接下来N行：每行包含M对字符，表示场地上的情况。字符对包括：".."表示空单元格，"R0"到"R9"和"B0"到"B9"表示球员，"RG"或"BG"表示球门，".Q"表示魁地奇球。
- 接下来一行：整数T，表示比赛步骤数。
- 接下来T行：每行描述一个动作，包含实体标识和动作描述。动作包括：移动（U、D、L、R）、接球（C）、扔球（T）。

输出数据格式：
- 每次得分时，输出得分时间（t）和得分队伍（RED或BLUE）。
- 比赛结束时，输出最终得分（红队得分r，蓝队得分b）。

请注意，这里的格式是LaTeX格式，实际输入输出时，字符对应当紧凑排列，没有空格。题目大意：模拟魁地奇比赛得分过程。比赛在一个N行M列的矩形场地上进行，场地可能包含球员、球门和魁地奇球（Quaffle）。比赛由T个步骤组成，每个步骤中，场上的一个实体（球员或球）执行一个动作。球员可以移动、接球或扔球。球员带着魁地奇球移动，当球员将球扔在对方球门中时，己方得一分，球会回到场地中央。如果球员将球扔在自己球门中，对方得一分。需要记录比赛过程中的得分情况，并在比赛结束时输出最终得分。 输入数据格式： - 第一行：整数N和M，表示场地的大小。 - 接下来N行：每行包含M对字符，表示场地上的情况。字符对包括：".."表示空单元格，"R0"到"R9"和"B0"到"B9"表示球员，"RG"或"BG"表示球门，".Q"表示魁地奇球。 - 接下来一行：整数T，表示比赛步骤数。 - 接下来T行：每行描述一个动作，包含实体标识和动作描述。动作包括：移动（U、D、L、R）、接球（C）、扔球（T）。 输出数据格式： - 每次得分时，输出得分时间（t）和得分队伍（RED或BLUE）。 - 比赛结束时，输出最终得分（红队得分r，蓝队得分b）。 请注意，这里的格式是LaTeX格式，实际输入输出时，字符对应当紧凑排列，没有空格。