P10545 [THUPC 2024 Finals] Robots

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

There are $n$ robots standing in a circle, numbered $0 \sim n-1$ in counterclockwise order. Each robot has two hands. Initially, for robot $i$, its “left hand” points to robot $l_i$, and its “right hand” points to robot $r_i$. Inside every robot, there is a “command”. The “commands” can have the following forms. ## Commands Below we describe the format of these “commands” and their effects when being “executed”. In the statements below, the word “itself” always refers to the robot that owns this “command”. - `SLACKOFF`: “slack off”, i.e. do nothing. - `MOVE h z`: Move the $h$-th hand counterclockwise by $z$ robots. When $h=0$, it means the “left hand”; when $h=1$, it means the “right hand”. The same applies below. - `SWAP`: Swap the “commands” of the two robots that its hands point to. - `TRIGGER : `: Here, `` is one of `SLACKOFF`, `MOVE`, `SWAP`, `TRIGGER`, `TOGGLETRIGGERREPLACE`; `` is a complete non-`TRIGGER` “command”. The `TRIGGER` command itself will not be “executed”. However, when some **other** robot finishes “executing” a “command”, and its “right hand” points to itself, then its `TRIGGER` command (if any) that satisfies the following conditions will be “triggered”, meaning that the corresponding `` will be “executed” once: - If `` is not `TRIGGER`, then the “command” that has just been executed is a `` command; - If `` is `TRIGGER`, then the “command” that has just been executed is the `` part executed when a `TRIGGER` command is “triggered”. - `TOGGLETRIGGERREPLACE h `: If the “command” of the robot pointed to by the $h$-th hand is a `TRIGGER` command, then “toggle” it into the `` part of that “command”, i.e. delete the leading `TRIGGER` and its condition part. If that “command” is not a `TRIGGER` command, suppose it is ``, then toggle it into `TRIGGER : `. Here, `` is one of `SLACKOFF`, `MOVE`, `SWAP`, `TRIGGER`, `TOGGLETRIGGERREPLACE`. Then modify its own “command” (note that this may include more than just the part currently being “executed”) into ``, where `` is a complete “command”. The output format when robots “execute” commands is as follows: - When “slacking off”, output `Robot slacks off.` where `` is an integer denoting the id of the robot “executing” the current “command”. The same applies below. - When “moving”, output `Robot moves its hand towards Robot .` where `` is `left` or `right`, indicating which hand is moved (`left` for “left hand”, `right` for “right hand”); `` is an integer denoting the id of the robot that this hand points to after moving. - When “swapping”, output `Robot swaps the commands of Robot and Robot .` where `` and `` are integers denoting the ids of the robots whose “commands” are “swapped”. These two numbers may be output in any order. - When “toggling”, output `Robot toggles the trigger property of the command of Robot `. - `TRIGGER` commands will not be “executed”, but when they are “triggered”, the corresponding “command” will be “executed” and output in the formats above. You selected some robots in a certain order (robots may be selected repeatedly) and “executed” their “commands”, obtaining the **complete** output of “execution”. That is, after the last “command” in the output is executed, no other “command” is “triggered”. However, you forgot the order in which you selected robots, and you also forgot what “command” each robot initially had. You only remember the total number of robots and where each robot’s hands initially point. You want to recover what the initial “command” of every robot was using all the known information.

The first line contains two positive integers $n,k$, where $k$ is the total number of output lines. The next $n$ lines each contain two integers $l_i,r_i$, given in increasing order of robot id. The next $k$ lines each contain one output message of an “executed” “command”. To reduce the burden of processing input, the output messages are simplified as follows (unless otherwise specified, the meanings of parameters are the same as above): - When “slacking off”, output `SLACKOFF `. - When “moving”, output `MOVE `, where `` is `0` or `1`, indicating which hand is moved (`0` for “left hand”, `1` for “right hand”). - When “swapping”, output `SWAP `. - When “toggling”, output `TOGGLETRIGGERREPLACE `. - `TRIGGER` commands will not be “executed”, but when they are “triggered”, the corresponding “command” will be “executed” and output in the formats above. The input guarantees that there exists a set of initial “commands” such that there is a way to select robots to obtain the given output. Constraints: $1\le n,k \le 500000$. Also, $0\le l_i,r_i

Output $n$ lines. Print the initial “command” of each robot in increasing order of robot id, one per line. You must ensure that the “command” format is correct, 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}$, then Special Judge is guaranteed to return the result correctly. In addition, any answer that can produce the $k$ lines of output in the input is considered correct.

**Sample Explanation 1** The order of selecting robots is $1,1,0,1,3$. The second and sixth “commands” executed are executed after triggering `TRIGGER` commands. Note that the triggering time of a `TRIGGER` command is after the previous “command” is executed. Therefore, after the first “swap”, since robot $1$’s “right hand” points to robot $0$, which has `TRIGGER SWAP: SWAP`, this `TRIGGER` command can be triggered. **Sample Explanation 2** The order of selecting robots is $0,3,0,1,3$. The fifth and sixth “commands” executed are executed after triggering `TRIGGER` commands. The first “execution” will change robot $1$’s “command” into `SWAP`, and robot $0$’s “command” into `MOVE 1 1`. The fifth “execution” will change robot $2$’s “command” from `SLACKOFF` to ``` TRIGGER TOGGLETRIGGERREPLACE: SLACKOFF ``` and robot $3$’s “command” from ``` TRIGGER SWAP: TOGGLETRIGGERREPLACE 1 TOGGLETRIGGERREPLACE SLACKOFF ``` to `SLACKOFF` rather than `TRIGGER SWAP: SLACKOFF`. **Sample Explanation 3** The order of selecting robots is $0$. The second, third, and fourth “commands” executed are executed after triggering `TRIGGER` commands. Note that after robot $3$ finishes “executing” its “command”, it will not then trigger its own `TRIGGER` “command”, even if its “right hand” points to itself. Also, selecting a robot that has a `TRIGGER` command will not produce any output, so doing so is meaningless. **Sample Explanation 4** See *4.in* under the problem directory. This sample does not provide sample output. **Sample Explanation 5** See *5.in* under the problem directory. This sample does not provide sample output. **Notes** We will provide an executable file `checker` to help you check whether your output is correct. Use it by running the following command in the directory where the file is located: ``` ./checker ``` If your output is correct, the program will output `Accepted.`; otherwise, it will indicate the earliest position where the “execution” result does not match the input file. Note that if the input file you use is not a sample input, this program will not check whether there exists a set of initial “commands” such that there is a way to select robots to obtain the corresponding “execution” result. **Source and Acknowledgements** From the THUPC2024 (Tsinghua University Student Programming Contest and Invitational Contest) finals. Thanks to THUSAA for providing the problem. For the testdata, statement, reference solution, editorial, etc., please refer to the official THUPC repository . Translated by ChatGPT 5