Description

To break through the blockade and land successfully, Steve used an electromagnetic jammer, causing the drones to start killing each other.

However, the situation quickly became chaotic, and it was impossible to understand what was happening.

Fortunately, Steve’s troops recorded the situation before the brawl started, and managed to obtain the order of operations executed by the drones.

Each drone has $5$ attributes: $atk,def,mat,mdf,fix$, its current health $hp$, its current coordinates $(x,y,z)$, its current horizontal facing $f$ (range $0$–$7$), and its vertical facing $h$ (range $0$–$4$).

At each moment, all surviving drones will first move one cell straight forward.

Then, the surviving drones will in increasing order of their IDs execute exactly one of the following operations:

• No operation (N).

• Turn up/down (U/D): change the value of $h$. Up means increase, down means decrease. If it goes out of range, the operation is invalid and should be ignored.

• Turn left/right (L/R): change the value of $f$. Left means increase, right means decrease, with wrap-around (corresponding to counterclockwise/clockwise when viewed from above).

For example, when $h=4$, operation U is invalid. When $f=0$, operation R will change $f$ to $7$.

• Repair (F): increase $hp$ by $fix$.

• Bullet (A): deal damage to the nearest drone located straight ahead of this drone. The damage value is the difference between the attacker’s current $atk$ and the target’s $def$ (if the difference is negative, it deals no damage). If multiple drones are at the same position, only the one with the smallest ID takes damage.

• Laser (M): deal damage to all drones straight ahead of this drone. The damage value is the difference between the attacker’s current $mat$ and the target’s $mdf$ (if the difference is negative, it deals no damage).

Note: drones overlapping with the firing drone will not take damage.

If after taking damage, $hp\leq 0$, then the drone crashes.

For $f$ and $h$, “straight ahead” is defined as follows:

First, determine the $x,y$ direction based on $f$, as shown in the figure below.

Then, further determine the direction based on $h$.

• For $h=0$ or $h=4$, straight ahead is straight down or straight up ($x,y$ unchanged, $z$ changes).

• For $h=1$ or $h=3$, based on the horizontal direction above, also move one cell down/up.

• For $h=2$, straight ahead is the horizontal direction ($x,y$ as above, $z$ unchanged).

(Some people reported that the direction is hard to understand. Here is the direct correspondence table of $f,h$ and the straight-ahead $(x,y,z)$.)

Now, Steve has told you the initial state of all drones and the operations they execute afterward.

You need to tell him, after $t$ moments of fighting, the position and health of each drone.

Input Format

The first line contains two integers $n,t$, representing the number of drones and the number of moments.

The next $n$ lines each contain $11$ integers and a string of length $t$, describing the drones in order of their IDs.

These $11$ integers are $x,y,z,h,f,atk,def,mat,mdf,hp,fix$, where $hp$ is the initial health.

Each character in the string is an uppercase letter, representing the operation at each of the $t$ moments in order.

Output Format

Output $n$ lines, each with $4$ integers $x,y,z,hp$.

If the drone has not crashed, output its coordinates and final health.

Otherwise, output its coordinates right before crashing, and output $0$ for $hp$.

4 7
-1 -1 0 2 1 1 0 0 0 5 0 RAAAAAA
51 0 1 1 4 0 0 1 0 5 0 UMMMMMM
-2 0 0 2 0 0 0 0 0 5 1 FFFNNNN
53 0 0 2 4 0 0 0 0 5 1 FFFNNNN

6 0 0 1
45 0 0 0
5 0 0 4
46 0 0 7

7 1
0 0 0 0 0 2 0 0 0 1 0 A
1 0 0 0 0 4 0 0 0 3 0 A
1 0 0 0 0 1 1 1 1 4 0 N
1 0 -1 0 0 0 0 0 0 2 0 N
0 1 0 0 0 0 0 3 0 3 0 M
0 1 -1 0 0 0 0 0 1 3 0 N
0 1 -1 0 0 0 0 0 2 3 0 N

0 0 -1 1
1 0 -1 3
1 0 -1 4
1 0 -2 2
0 1 -1 3
0 1 -2 1
0 1 -2 2

Hint

After two drones move and change their facing directions, they end up facing each other. Then they both fire crazily at each other. In the end, Drone $1$ shoots down Drone $2$ first. Since Drone $2$ has already crashed, Drone $1$ will not be shot down.

Behind them there are two drones following respectively. Drone $2$ uses a laser, so Drone $3$ will also take damage. Drone $1$ uses bullets, so Drone $4$ will not take damage. This continues until Drone $2$ crashes, after which Drone $1$ fires one last bullet and deals $1$ point of damage to Drone $4$. At the same time, in their first three operations, both drones performed three repairs, so $hp$ increases by $3$.

During judging, each Subtask includes 3 test points. You can get the score of that Subtask only if you pass all of them.

Sample 2 explanation: https://www.luogu.com.cn/discuss/582252

Constraints:

$1\leq n,t\leq 100$

All input numbers are within reasonable ranges, and their absolute values are all at most $100$.

Among them, $atk,def,mat,mdf,fix$ are non-negative integers.

$hp$ is a positive integer.

$x,y,z$ are integers.

$h$ is one of $0,1,2,3,4$.

$f$ is one of $0,1,2,3,4,5,6,7$.

The string contains only $8$ kinds of characters: $NFLRUDAM$.

In addition, for the first 3 subtasks, it is guaranteed that at any moment, the drones’ $z$ coordinates are $0$.

Translated by ChatGPT 5