Problem Background

Note that the instruction meanings in this problem are slightly different from those in the preliminary round.

Problem Description

There are $n$ robots arranged in a circle, numbered in counterclockwise order from $0$ to $n-1$.

Each robot has two hands. The robot numbered $i$ initially points its "left hand" to the robot numbered $l_i$ and its "right hand" to the robot numbered $r_i$.

Each robot contains an "instruction" within it. The "instructions" can be in the following formats:

Instructions

Below are the formats of these "instructions" and their effects when "executed." The term "self" refers to the robot that owns the "instruction."

• SLACKOFF: "Slack off", meaning do nothing.
• MOVE h z: Move the $h$-th hand counterclockwise by $z$ robot positions. When $h=0$, it refers to the "left hand"; when $h=1$, it refers to the "right hand".
• SWAP: "Swap" the "instructions" of the robots pointed to by both hands.
• TRIGGER <COMMANDNAME>: <COMMAND>: Where <COMMANDNAME> is one of SLACKOFF, MOVE, SWAP, TRIGGER, TOGGLETRIGGERREPLACE; <COMMAND> represents a complete non-TRIGGER "instruction". The TRIGGER instruction itself is not "executed", but when another robot "executes" an instruction and its "right hand" points to self, a TRIGGER instruction (if any) that meets the following conditions will be "triggered"—executing the corresponding <COMMAND>:
• If <COMMANDNAME> is not TRIGGER, the last "executed" instruction was a <COMMANDNAME> instruction.
• If <COMMANDNAME> is TRIGGER, the last "executed" instruction was a <COMMAND> part of a TRIGGER instruction that was "triggered".
• TOGGLETRIGGERREPLACE h <COMMANDNAME> <NEWCOMMAND>: If the "instruction" of the robot pointed to by the $h$-th hand is a TRIGGER instruction, switch it to the <COMMAND> part, i.e., remove the TRIGGER and condition part; if this "instruction" is not a TRIGGER instruction, suppose it is <COMMAND>, switch it to TRIGGER <COMMANDNAME>: <COMMAND>. Where <COMMANDNAME> is one of SLACKOFF, MOVE, SWAP, TRIGGER, TOGGLETRIGGERREPLACE. Then modify self's "instruction" (note this may include more than just the part being "executed") to <NEWCOMMAND>. Where <NEWCOMMAND> is a complete "instruction".

The output format when robots "execute" various "instructions" is as follows:

• When "slacking off", output Robot <id> slacks off.. Where <id> is an integer representing the robot number executing the current "instruction".
• When "moving", output Robot <id> moves its <side> hand towards Robot <id2>.. Where <side> is left or right, indicating which hand was moved (left for "left hand", right for "right hand"); <id2> is an integer representing the robot number the hand now points to.
• When "swapping", output Robot <id> swaps the commands of Robot <id2> and Robot <id3>.. Where <id2> and <id3> are integers representing the robot numbers whose "instructions" were swapped, and these numbers can be output in any order.
• When "toggling", output Robot <id> toggles the trigger property of the command of Robot <id2>.
• TRIGGER instructions are not "executed", but when they are "triggered", they output the corresponding "executed" information in the above format.

You have executed the "instructions" of some robots (possibly repeatedly) in a certain order, obtaining the complete output of the "executions". That is, after the last "instruction" in the output is "executed", no other "instructions" are "triggered". However, you have forgotten the order in which you selected the robots and what "instructions" each robot initially had. You only remember the total number of robots and what positions each robot's hands initially pointed to.

You want to restore the initial "instructions" of all robots based on all the known information.

Input and Output Formats

Input Format

The first line contains two positive integers $n, k$, where $k$ represents the total number of output lines.

The next $n$ lines, each containing two integers $l_i, r_i$, input in ascending order of robot numbers.

The next $k$ lines, each containing an output message of an "executed" instruction.

To ease input processing, the output messages are simplified as follows (with parameter meanings as above):

• When "slacking off", output SLACKOFF <id>.
• When "moving", output MOVE <id> <side> <id2>. Where <side> is 0 or 1, indicating which hand was moved (0 for "left hand", 1 for "right hand").
• When "swapping", output SWAP <id> <id2> <id3>.
• When "toggling", output TOGGLETRIGGERREPLACE <id> <id2>.
• TRIGGER instructions are not "executed", but when they are "triggered", they output the corresponding "executed" information in the above format.

The input guarantees that there exists an initial set of "instructions" such that there is a way to select robots to produce the corresponding output.

It is guaranteed that $1 \le n, k \le 500000$.

It is guaranteed that $0 \le l_i, r_i < n$.

Output Format

Output $n$ lines, outputting the initial "instructions" of the robots in ascending order of their numbers, one per line.

You must ensure that the "instructions" are correctly formatted and that $0 \le z < n$.

You must ensure that your output file is not too large. If your output file size does not exceed $100\texttt{MB}$, the Special Judge will definitely return the correct result.

Any answer that can produce the $k$ lines of output in the input is considered correct.

Sample Input and Output

Sample Input #1

4 7
1 3
2 0
3 0
2 1
SWAP 1 0 2
SWAP 0 1 3
SWAP 1 2 0
MOVE 0 0 2
SWAP 1 0 2
SWAP 0 2 3
MOVE 3 0 3

Sample Output #1

MOVE 0 1
SWAP
TRIGGER SWAP: SWAP
SWAP

Sample Input #2

4 7
1 2
2 3
3 1
0 2
TOGGLETRIGGERREPLACE 0 1
SLACKOFF 3
MOVE 0 1 3
SWAP 1 2 3
TOGGLETRIGGERREPLACE 3 2
SLACKOFF 2
SLACKOFF 3

Sample Output #2

TOGGLETRIGGERREPLACE 0 MOVE MOVE 1 1
TRIGGER SLACKOFF: SWAP
TRIGGER SWAP: TOGGLETRIGGERREPLACE 1 TOGGLETRIGGERREPLACE SLACKOFF
SLACKOFF

Sample Input #3

4 4
2 1
1 2
0 3
1 3
SLACKOFF 0
SLACKOFF 1
SLACKOFF 2
SLACKOFF 3

Sample Output #3

SLACKOFF
TRIGGER SLACKOFF: SLACKOFF
TRIGGER SLACKOFF: SLACKOFF
TRIGGER TRIGGER: SLACKOFF

Notes

Sample Explanation 1

The order of robot selection is $1, 1, 0, 1, 3$, where the second and sixth "executed" instructions are "triggered" TRIGGER instructions.

Note that TRIGGER instructions are "triggered" after the previous instruction is "executed", so after the first swap, since robot $1$'s "right hand" points to robot $0$ with TRIGGER SWAP: SWAP, this TRIGGER instruction can be "triggered".

Sample Explanation 2

The order of robot selection is $0, 3, 0, 1, 3$, where the fifth and sixth "executed" instructions are "triggered" TRIGGER instructions.

The first "execution" changes robot $1$'s "instruction" to SWAP and robot $0$'s "instruction" to MOVE 1 1.

The fifth "execution" changes robot $2$'s "instruction" from SLACKOFF to

TRIGGER TOGGLETRIGGERREPLACE: SLACKOFF

, and robot $3$'s "instruction" from

TRIGGER SWAP: TOGGLETRIGGERREPLACE 1 TOGGLETRIGGERREPLACE SLACKOFF

to SLACKOFF instead of TRIGGER SWAP: SLACKOFF.

Sample Explanation 3

The order of robot selection is $0$, where the second, third, and fourth "executed" instructions are "triggered" TRIGGER instructions.

Note that after robot $3$ "executes" its "instruction", it does not "trigger" its own TRIGGER instruction, even though its "right hand" points to itself.

Also, selecting a robot with a TRIGGER instruction does not produce any output, so doing so is meaningless.

Sample Explanation 4

See 4.in in the problem directory. This sample does not provide sample output.

Sample Explanation 5

See 5.in in the problem directory. This sample does not provide sample output.

Hints

We will provide an executable file checker to help you check if your output is correct. The usage is as follows:

./checker <input file path> <your output file path>

If your output is correct, the program will output Accepted.; otherwise, it will indicate the earliest mismatch with the input file.

Note that if your input file is not the sample input, the program will not check if there exists an initial set of "instructions" such that there is a way to select robots to produce the corresponding "execution" result.

Source and Acknowledgements

From THUPC2024 (2024 Tsinghua University Student Programming Contest and University Invitational). Thanks to THUSAA for providing the problem.

For data, problem statements, standard solutions, and editorials, please refer to the THUPC official repository https://thusaac.com/public

见题面 Input 部分

见题面 Output 部分