Problem Background

Steve leads his team to M-star to eliminate the dark forces. As they are about to land, they are intercepted by drones in the sky of M-star.

Problem Description

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

However, the situation quickly becomes chaotic, and it is impossible to understand the current state.

Fortunately, Steve's team has recorded the situation before the chaos began and has managed to obtain the sequence of operations executed by the drones.

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

At each moment, all surviving drones first move one grid forward in the positive direction.

Then, surviving drones in ascending order of their numbers execute one of the following operations:

• No operation (N)
• Turn up/down (U/D): Change the value of $h$, up increases, down decreases. If it exceeds the range, it is an invalid operation and is ignored.
• Turn left/right (L/R): Change the value of $f$, left increases, right decreases, cycling (counterclockwise and clockwise respectively when viewed from above).
• Example: When $h=4$, operation U is invalid. When $f=0$, operation R changes $f$ to 7.
• Repair (F): Increase $hp$ by $fix$ points.
• Bullet (A): Inflict damage on the nearest drone directly in front. The damage is the difference between the current drone's $atk$ and the target's $def$ (negative difference means no damage). If multiple drones are at the same position, only the drone with the smallest number takes damage.
• Laser (M): Inflict damage on all drones directly in front. The damage is the difference between the current drone's $mat$ and the target's $mdf$ (negative difference means no damage).

Note: Drones overlapping with the firing drone do not take damage.

If a drone's $\leq 0$ after taking damage, it crashes.

For $f$ and $h$, their "forward direction" is defined as follows:

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

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

• For $h=0$ or $h=4$, the forward direction is straight down or up ($x, y$ unchanged, $z$ changes).
• For $h=1$ or $h=3$, move one grid down/up in addition to the above direction.
• For $h=2$, the forward direction is horizontal ($x, y$ as described, $z$ unchanged).

(A table correlating $f, h$ with the forward direction $(x, y, z)$ is provided below for clarity.)

Now, Steve has provided the initial states of all drones and the operations they will execute.

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

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 containing 11 integers and a string of length $t$, describe the drones in ascending order of their numbers.

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

The string consists of uppercase letters, each representing the operation for each moment in sequence.

Output Format

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

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

Otherwise, output its coordinates before crashing, with $hp$ as 0.

Sample Input and Output

Input Sample #1

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

Output Sample #1

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

Input Sample #2

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

Output Sample #2

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

Notes/Hints

Two drones move and change direction to face each other, then they start firing at each other. Eventually, the 1st drone shoots down the 2nd drone first, and since the 2nd drone has crashed, the 1st drone is not shot down.

Behind them, two other drones follow. The 2nd drone uses a laser, so the 3rd drone also takes damage. The 1st drone uses bullets, so the 4th drone does not take damage until the 2nd drone crashes, after which the 1st drone's final bullet inflicts one point of damage on the 4th drone. Meanwhile, the two drones perform three repairs each in the first three operations, increasing their $hp$ by 3.

During testing, each Subtask includes 3 test cases, and you must pass all of them to earn the points for that Subtask.

Data Range:

$1 \leq n, t \leq 100$

All input numbers are within reasonable ranges, with absolute values not exceeding 100.

$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 the 8 characters: $N, F, L, R, U, D, A, M$.

Additionally, for the first 3 subtasks, the z-coordinate of any drone at any time is guaranteed to be 0.

见题面 Input 部分

见题面 Output 部分