Background

Note that the meaning of the instructions in this problem differs slightly from those in the preliminary round.

Description

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

Each robot has two hands. Initially, the "left hand" of robot $i$ points to robot $l_i$, and the "right hand" points to robot $r_i$.

Every robot has an "instruction" written inside it. The instructions are of the following forms:

Instructions

The following describes the format of these "instructions" and their effects when "executed". The term "self" refers to the robot that possesses the instruction.

• SLACKOFF: Does nothing.
• MOVE h z: "Moves" the $h$-th hand $z$ positions in the counter-clockwise direction. $h=0$ denotes the "left hand", and $h=1$ denotes the "right hand".
• SWAP: "Swaps" the instructions of the robots pointed to by the two hands.
• TRIGGER <COMMANDNAME>: <COMMAND>: Here, <COMMANDNAME> is one of SLACKOFF, MOVE, SWAP, TRIGGER, or TOGGLETRIGGERREPLACE; <COMMAND> represents a complete non-TRIGGER instruction. The TRIGGER instruction itself is not "executed". However, after another robot finishes "executing" an instruction, if its "right hand" points to self, and self satisfies the following condition, the TRIGGER instruction (if any) will be "triggered"—meaning the corresponding <COMMAND> is "executed":
  • If <COMMANDNAME> is not TRIGGER, the instruction just "executed" must be a <COMMANDNAME> instruction.
  • If <COMMANDNAME> is TRIGGER, the instruction just "executed" must be the <COMMAND> part of a TRIGGER instruction that was just "triggered".
• TOGGLETRIGGERREPLACE h <COMMANDNAME> <NEWCOMMAND>: If the instruction of the robot pointed to by the $h$-th hand is a TRIGGER instruction, "toggle" it to the <COMMAND> part of that instruction (i.e., remove the TRIGGER and condition part). If the instruction is not a TRIGGER instruction, assuming it is <COMMAND>, "toggle" it to TRIGGER <COMMANDNAME>: <COMMAND>. Here, <COMMANDNAME> is one of SLACKOFF, MOVE, SWAP, TRIGGER, or TOGGLETRIGGERREPLACE. Then, modify self's instruction (note that this may contain more than just the part currently being "executed") to <NEWCOMMAND>. <NEWCOMMAND> is a complete instruction.

The output format when a robot "executes" an instruction is as follows:

• For SLACKOFF, output Robot <id> slacks off.. <id> is the integer ID of the robot executing the instruction.
• For MOVE, output Robot <id> moves its <side> hand towards Robot <id2>.. <side> is left or right; <id2> is the ID of the robot the hand points to after the move.
• For SWAP, output Robot <id> swaps the commands of Robot <id2> and Robot <id3>.. <id2> and <id3> are the IDs of the robots whose instructions are swapped.
• For TOGGLETRIGGERREPLACE, 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 information of the corresponding instruction being "executed" in the format above.

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

You want to reconstruct the initial instructions of all robots using all the known information.

Input

The input is read from standard input.

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

The next $n$ lines each contain two integers $l_i, r_i$, given in order of increasing robot ID.

The next $k$ lines each contain an output message from an "executed" instruction.

To simplify input processing, the output messages are simplified as follows (parameters not specified have the same meaning as above):

• For SLACKOFF, output SLACKOFF <id>.
• For MOVE, output MOVE <id> <side> <id2>. <side> is 0 or 1.
• For SWAP, output SWAP <id> <id2> <id3>.
• For TOGGLETRIGGERREPLACE, output TOGGLETRIGGERREPLACE <id> <id2>.
• TRIGGER instructions are not "executed", but when they are "triggered", they output the information of the corresponding instruction being "executed" in the format above.

It is guaranteed that there exists a set of initial instructions such that there is a sequence of robot selections that produces the corresponding output.

Constraints: $1 \le n, k \le 500,000$, $0 \le l_i, r_i < n$.

Output

Output to standard output.

Output $n$ lines, representing the initial instructions of the robots in order of increasing ID.

You must ensure the instruction format is correct and $0 \le z < n$.

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

Any answer that produces the $k$ lines of output provided in the input is considered correct.

Examples

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

Output 1

MOVE 0 1
SWAP
TRIGGER SWAP: SWAP
SWAP

Note 1

The sequence of robot selections is $1, 1, 0, 1, 3$. The second and sixth instructions executed were triggered by TRIGGER instructions.

Note that a TRIGGER instruction is triggered after the previous instruction is executed. Therefore, after the first SWAP, since robot $1$'s "right hand" points to robot $0$ (which contains TRIGGER SWAP: SWAP), this TRIGGER instruction is triggered.

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

Output 2

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

Note 2

The sequence of robot selections is $0, 3, 0, 1, 3$. The fifth and sixth instructions executed were triggered by 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 (not TRIGGER SWAP: SLACKOFF).

Input 3

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

Output 3

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

Note 3

The sequence of robot selections is $0$. The second, third, and fourth instructions executed were triggered by TRIGGER instructions.

Note that after robot $3$ finishes executing an instruction, it does not immediately trigger its own TRIGGER instruction, even if its "right hand" points to itself.

Additionally, selecting a robot that contains a TRIGGER instruction produces no output, so doing so is meaningless.

Hint

We provide an executable file checker to help you verify if your output is correct. Use it in the directory containing the file with the following command:

./checker <input_file_path> <your_output_file_path>

If your output is correct, the program will output Accepted.; otherwise, it will indicate where the execution result first mismatches the input file.

Note that if the input file you use is not one of the sample inputs, this program will not check whether there exists a set of initial instructions that could produce the corresponding execution result.