Description

As everyone knows, student Xiao Cong is good at calculation, especially at computing binomial coefficients.

Now we have an $N \times M$ board, and some cells on the board contain obstacles. There are $K$ pieces on the board. Each piece belongs to either the red team or the blue team. Also, each piece has two attributes; for piece $i$, the two attributes are denoted by $a_i, b_i$, and it is guaranteed that $a_i \geq b_i$. Since there are two teams, Xiao Cong wants to play a game. The game has a total of $R$ rounds. In each round, every piece acts in the following order:

0. At the start of the round, let the current round be the $H$-th round. If this is the start of the game, then $H = 1$.

1. For all pieces that can move, move one cell forward in their current direction. Each piece’s direction must be one of up, down, left, or right. If a piece finds that it cannot move, i.e., the cell in front is outside the board or is an obstacle, then it does not move forward. Instead, it rotates its direction by $180^\circ$ (i.e., turns around). Note that after turning around, the piece will not move in this round.

2. For all pieces, each piece has exactly one skill. Now all pieces release skills in order of increasing index; if a piece cannot release its skill, it is skipped. There are the following kinds of skills:

   1. Heavy Hammer Sparkles (toolihai): Centered on itself, it creates gorgeous fireworks that are pleasing to the eye, with no effect.

   2. King of Face (faceking): This piece is full of “face”, and all pieces must obey its command, forcing all pieces to rotate their directions $90^\circ$ to the left (counterclockwise). The effect lasts permanently.

   3. Hair Gone (onepunch): After losing all its hair, Captain Wang becomes stronger, greatly boosting this piece’s attributes. That is, if the current attributes of piece $i$ are $\left(a_i, b_i\right)$, and the boost value is $v$, then its attributes become $\left(a_i + v, b_i\right)$. This effect lasts for $l$ rounds. If the current round is $H$, then this effect disappears at the start of round $H + l$. If before the effect disappears piece $i$’s attributes are $\left(a_i, b_i\right)$, then after the effect disappears its attributes become $\left(\max\left(a_i - v, 0\right), \min\left(b_i, \max\left(a_i - v, 0\right)\right)\right)$. Note that before the effect disappears, this skill may be released again; multiple releases stack, but the disappearance time is computed separately for each release. (See the second sample.)

   4. Rabi Ribi (rabiribi): Swings a real heavy hammer to create sparks, knocking back all enemy units in a forward fan-shaped area. The affected range is a forward fan-shaped area of size $v$, as shown below:

      

      From the figure, we can see that the piece releasing the skill is at the bottom, facing up, so the skill direction is also up. All cells above form the fan-shaped area affected by the skill. The fan size is $5$, i.e., $v = 5$. Note that some positions on the board have obstacles, and obstacles affect the skill range. If an obstacle lies within the skill range, then the fan-shaped area within the skill range starting from that obstacle will not be affected by the skill. In the figure, the lowest cell of each black column is an obstacle, and all black cells are cells that cannot be affected due to the obstacle.

      On the other hand, the knockback effect is defined as forcing a piece affected by the skill to move one cell along the skill direction, i.e., from $p_2$ being knocked back to position $p_3$ in the figure. If the knockback direction hits an obstacle or the board boundary, then handle it as follows:

      • If the next position is an obstacle, then it is knocked back to the cell behind that obstacle, i.e., from $p_0$ knocked back to $p_1$ in the figure.
      • If the next position is outside the board, e.g., currently in the first row and it would be knocked back to row $0$, then it is knocked back to the cell in row $N$ in the same column.

      Repeat the above process until it is knocked back to a position that is neither an obstacle nor outside the board; then the knockback process ends. (See the first sample.)

   5. Dropout Fireworks (firework): After dropping out, there is more time to dig holes. It makes the piece that most recently released Heavy Hammer Sparkles unable to move for the next $l$ rounds. If no such piece exists, then it makes itself unable to move for the next $l$ rounds.

   6. Save Uganda (viuganda): Uses vim to save fallen pieces, reviving the farthest dead allied piece from itself. If there is no dead allied piece, then revive the closest dead enemy piece from itself. If the enemy also has no dead pieces, do nothing. The distance used here is Manhattan distance: if piece $i$ is at $\left(x_i, y_i\right)$ and piece $j$ is at $\left(x_j, y_j\right)$, then the distance is $\left|x_i - x_j\right| + \left|y_i - y_j\right|$. If multiple pieces have the same Manhattan distance to the current piece, choose the one with the largest index. If the revived piece can release its skill in the current round and has not been skipped yet, it will release its skill.

   7. Dimensionality Reduction Strike (2dsaigao): Uses a hyperspace weapon to fire a dynamic light wave to its right-front, making units in some area unable to release skills. After the light wave is fired, when it hits the board edge or an obstacle, its direction changes as shown below:

      

      The center cell is where the current piece is, and its direction is left. Each time the light wave is about to enter a cell with an obstacle or the board edge, it rotates its direction $90^\circ$ clockwise. Each time the light wave travels from the center of one cell to the center of another, we say it travels a distance of $1$. After the wave has traveled a distance of $o$, it explodes centered at the current cell, making all pieces whose Manhattan distance to that cell is at most $v$ unable to release skills for the next $l$ rounds, i.e., they cannot release skills from now until the start of round $H + l$. (See the first sample.)

   8. Gugu Gugu (gugugugu): In life, you must never “pigeon” others in an ordinary way; if you pigeon, you must pigeon everyone together. This skill makes all allied pieces that have not released their skill yet in the current round skip the skill-releasing stage, i.e., allied pieces that have not yet released their skill cannot release their skill in the current round.

   9. Backward Propagation (backward): Stop time, reverse the game, and return itself to the past, to some previous round. If the current round is $H$, and this effect returns to $l$ rounds earlier, then piece $i$ will return to round $H - l$. “Returning to round $H - l$” means that all of the following values of piece $i$ revert to their values at the start of round $H - l$:

      • Position and direction.
      • Attributes.
      • Whether it is alive and its revival time.
      • Skill effects applied to it and their remaining durations.

      Note that the skill cooldown time of piece $i$ does not revert to the time of round $H - l$. (See the third sample.) (The skill cooldown rules are explained below.)

   10. Praise of Scallions (hupraise): The arrival of scallions makes today a sacred day, and red and blue pieces should be paired. Each red piece can be paired with any blue piece, and each piece can be paired with at most one opposing piece. Pieces $i$ and $j$ can be paired if they are from different teams and $a_i \oplus a_j$ is a multiple of $3$ (this symbol is XOR). Now every time this skill is activated, you need to find the maximum number of pairs that can be formed.

   Skill cooldown rules: For all skills, if the current round is $H$ and piece $i$ releases its skill, then the skill will not finish cooling down until round $H + z_i$, and it can only be released again after that. If piece $i$ is affected in the current round by a skill lasting $l$ rounds, then the effect will be removed at the start of round $H + l$. For all pieces, if its first skill cooldown time is $f_i$ and its cooldown interval is $z_i$, then without influence from other pieces, it will release its skill for the first time in round $f_i$, and then once every $z_i$ rounds thereafter.

3. For all cells on the board, if a cell contains both red pieces and blue pieces, then the pieces in that cell will engage in combat. The combat rules are as follows:

   We define the combat power of piece $i$ as $\binom{a_i}{b_i}$ (this is equivalent to $C_{a_i}^{b_i}$). In combat, each time both teams send out their own piece with the highest combat power in this cell to fight. Suppose the red team sends piece $i$ and the blue team sends piece $j$. If their combat powers are equal, then both pieces die. If they are not equal, suppose piece $i$ has higher combat power, then piece $j$ dies, and the two attributes of piece $i$ become $\max\left(a_i - a_j, 0\right), \max\left(b_i - a_j, 0\right)$. Repeat the above process until all pieces of one team in the cell have died. If piece $i$ dies in the current round, i.e., round $H$, then it will revive at the start of round $H + r_i$. After reviving, its two attributes return to the initial attribute values at the start of the game, and all skill effects on it are removed; its movement direction remains the same as before it died. During death, its skill cooldown proceeds normally, but it cannot move or release skills, and it is not affected by any other skills.

Now Xiao Cong tells you everything related to this game. You need to simulate the game according to the rules and output the position of each piece after the game ends.

Input Format

The input contains multiple test cases. The first line contains an integer $T$ indicating the number of test cases. Each test case is described as follows:

• The first line contains four integers $N, M, K, R$.

• The next $N$ lines each contain $M$ numbers. For the number in row $i$, column $j$, if it equals $0$, it means the cell at row $i$, column $j$ is a normal cell; otherwise, it is an obstacle.

• The next $K$ lines each start with nine integers $x_i, y_i, a_i, b_i, c_i, d_i, f_i, z_i, r_i$, describing piece $i$. Its initial position is at row $x_i$, column $y_i$, its attributes are $a_i, b_i$, and its team is $c_i$. If $c_i = 0$ it is red; otherwise it is blue. The initial facing direction is $d_i$, where $d_i = 0, 1, 2, 3$ represent up, down, left, right. $f_i$ is the first cooldown time, and $z_i$ is the cooldown interval, i.e., if not affected by other pieces, piece $i$ releases its skill for the first time in round $f_i$, and then once every $z_i$ rounds. $r_i$ is its revival time. Then there is a string $s_i$, which is the English name of its skill, already given after each skill above. For different skill types, additional values are appended on the same line as follows:

  1. Heavy Hammer Sparkles (toolihai): no additional input.

  2. King of Face (faceking): no additional input.

  3. Hair Gone (onepunch): additional input $v_i, l_i$, representing the boost value and duration.

  4. Rabi Ribi (rabiribi): additional input $v_i$, representing the skill range.

  5. Dropout Fireworks (firework): additional input $l_i$, representing the duration of the effect.

  6. Save Uganda (viuganda): no additional input.

  7. Dimensionality Reduction Strike (2dsaigao): additional input $y_i, v_i, l_i$, representing the travel distance of the wave, the affected range after explosion, and the duration of the effect.

  8. Gugu Gugu (gugugugu): no additional input.

  9. Backward Propagation (backward): additional input $l_i$, meaning returning to $l_i$ rounds earlier. The data guarantees it will not return to before the start of the game.

  10. Praise of Scallions (hupraise): no additional input.

Output Format

For each test case:

• Every time skill $10$ is activated, output one line containing one integer.

• After the game ends, output $K$ lines. Each line contains two integers indicating the current row and column of piece $i$.

4
2 4 4 2
0 0 0 0
0 0 0 1
1 2 1 1 0 2 1 10 1 2dsaigao 1 0 20
2 1 1 1 0 0 1 10 1 faceking
2 1 1 1 0 3 1 10 1 rabiribi 1
1 3 1 1 0 1 1 10 1 toolihai
1 5 4 4
0 0 0 0 0
1 1 2 2 0 3 1 1 100 onepunch 1 2
1 2 1 1 1 0 1 1 100 toolihai
1 3 1 1 1 0 1 1 100 toolihai
1 4 2 1 1 0 1 1 100 toolihai
1 4 1 4
0 0 0 0
1 1 1 1 0 3 3 2 2 backward 2
10 10 10 20
0 0 0 1 0 1 0 0 0 1
0 0 0 0 0 0 0 0 0 1
0 1 0 0 1 0 0 1 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0 0 1
0 1 0 0 0 0 0 0 0 0
1 0 0 0 1 0 1 0 1 1
0 0 0 0 0 0 0 0 0 1
0 0 1 0 1 1 0 1 0 1
1 0 0 0 0 0 0 0 0 0
10 9 8 0 0 1 6 7 2 viuganda
5 3 10 0 1 1 6 3 7 toolihai
2 7 6 3 0 3 7 3 1 faceking
5 7 10 9 1 3 9 8 8 rabiribi 10
6 10 1 1 0 1 11 7 7 backward 9
2 3 8 5 0 3 2 9 4 onepunch 6 1
1 7 8 2 0 3 11 2 5 hupraise
9 9 4 3 1 3 12 4 9 gugugugu
2 1 10 6 1 2 6 6 2 2dsaigao 9 9 9
10 10 10 5 1 1 12 4 8 firework 4

1 1
1 1
2 3
2 1
1 4
1 2
1 3
1 4
1 2
5
10 6
2 5
1 5
5 8
6 10
1 7
1 5
8 9
4 9
8 1

Hint

Sample Explanation

For the first sample, when skill $7$ is released at the upper-left, the dynamic light wave is fired toward the corner. When it hits the corner and bounces back to the firing point, the distance is $1$, so it explodes in place, making skill $2$ unable to be released. The lower-right part shows an example of using skill $4$ to knock the opponent through the map.

For the second sample, the first piece releases its skill every time it moves one step to the right. In the first round it moves to $(1, 2)$, after releasing the skill its attributes become $(3, 2)$, and after fighting the opponent its attributes become $(2, 1)$. In the second round it moves to $(1, 3)$, after releasing the skill its attributes become $(3, 1)$, and after fighting the opponent its attributes become $(3, 0)$. In the third round it moves to $(1, 4)$. Since the skill effect released in the first round disappears, its attributes revert to $(2, 0)$, then it releases the skill again to become $(3, 0)$, and then it is beaten to death by the opponent. So it finally stays at $(1, 4)$.

For the third sample, the piece releases its skill every two moves to jump back to the state two rounds ago, and repeats this cycle.

Constraints

It is guaranteed that $1 \leq T \leq 20$, $1 \leq N, M \leq 100$, $1 \leq K \leq 200$, $1 \leq R \leq 1000$.

It is guaranteed that among all additional inputs, except that the durations of skills $3, 5, 7$ are greater than $0$, all others are at least $0$.

It is guaranteed that no piece starts on an obstacle, and both the initial and boosted attribute values do not exceed $1000$ (but it is not guaranteed that attributes after boosts are at most $1000$).

It is guaranteed that the first cooldown time, the cooldown interval, and the revival time are all greater than $0$.

Copyright Information

From Tsinghua University Programming Contest and Collegiate Invitational 2018 (THUPC2018). Thanks to Pony.ai for supporting this contest.

Solutions and other resources can be found at https://github.com/wangyurzee7/THUPC2018.

Translated by ChatGPT 5