Little Q recently discovered a new game where the goal is to progress from a novice to a legendary martial arts master.
In the complex world of the game, Little Q must make careful choices for every situation he faces. For example, whether to accept a challenge from a stranger, or whether to agree to trade a precious sword for someone else's secret martial arts manual. Every choice Little Q makes may affect his future development: if he actively challenges a master, he might suffer heavy losses; but if he avoids the challenge, he might never see that master again.
Little Q played this game many times but could not reach his desired ending, so he went to great lengths to find the game's script. Surprisingly, the script is not like the scripts we usually see; instead, it resembles code. The script is described as follows:
Quantities: There are 2 types of quantities: constants and variables.
Constants: An integer.
Variables: Mutable integers with an initial value of $0$. Different variables are distinguished by different positive integers.
Events: The entire script consists of several events. All events are numbered sequentially starting from $1$ in the given order. There are 3 types of events: normal events, choice jumps, and conditional jumps.
Execution Position: An integer representing the number of the next event to be executed. If an event with this number does not exist, the execution stops, meaning the game has reached an ending. Initially, the execution position is $1$.
Normal Event: A variable increases or decreases by the value of a quantity. After this, the execution position increases by $1$.
Choice Jump: Two integers. When execution reaches this point, the player must choose one of these two integers, and the execution position will be updated to the chosen integer.
Conditional Jump: Two quantities and two integers. When execution reaches this point, if the first quantity is less than the second quantity, the execution position is updated to the first integer; otherwise, it is updated to the second integer.
Little Q believes that the entire game aims to maximize a variable called "Achievement Value" (numbered $1$).
Input
The first line of the input contains two positive integers $n$ and $m$, representing the number of events and the number of variables, respectively.
The next $n$ lines each describe an event. These events are numbered $1$ to $n$ in the order they are given.
The format for describing quantities and events is as follows (where "#" in the "Format" column represents a space).
| Type | Format | Example |
|---|---|---|
| Constant | c#integer | c -2 |
| Variable | v#positive integer | v 5 |
| Normal Event | variable#+#quantity variable#-#quantity |
v 1 + c -1 v 2 - v 2 |
| Choice Jump | s#integer1#integer2 | s 10 20 |
| Conditional Jump | i#quantity1#quantity2#integer1#integer2 | i c 99 v 2 0 1 |
Output
Each file should contain several lines, with each line containing the character "1" or "2", representing the choice made at each choice jump encountered during execution.
The number of lines in the output must be strictly equal to the number of choice jumps encountered during the execution of the game.
Examples
Input 1
11 2 v 2 + c 19 i v 2 c 3 7 3 s 4 7 v 1 + c 13 v 2 - c 3 i c 0 c 1 2 0 i v 2 c 5 12 8 s 9 12 v 1 + c 23 v 2 - c 5 i c 0 c 1 7 0
Output 1
1 1 1 2 1 1
Note 1
According to the scheme in the sample output, the execution position changes as follows:
1 → 2 → 3 → 4 → 5 → 6 → 2 → 3 → 4 → 5 → 6 → 2 → 3 → 4 → 5 → 6 → 2 → 3 → 7 → 8 → 9 → 10 → 11 → 7 → 8 → 9 → 10 → 11 → 7 → 12
When the execution position becomes $12$, the script ends. The final value of variable $1$ is $85$.
Event $1$ increases variable $2$ by $19$, which can be considered as obtaining $19$ units of initial capital.
Event $6$ is an unconditional jump to event $2$, which is a loop. From events $2$ and $3$, it can be seen that if variable $2$ is less than $3$ (insufficient capital for one purchase) or if the player chooses to give up, the loop will be exited.
Events $4$ and $5$ within the loop spend $3$ units of capital to gain $13$ achievement points.
Events $7$ to $11$ are a similar loop, but with different parameters. They spend $5$ units of capital to gain $23$ achievement points.
Scoring
For each data set, we score it as follows: if your output is invalid, you get $0$ points. If your output executes more than $10^6$ lines of the script, you get $0$ points. If your output allows the script to terminate normally, you get $1$ point. If your output allows the script to terminate normally and the achievement value is positive at the end, you get $2$ points. We have set $8$ scoring parameters $a_3, a_4, \dots, a_{10}$. If your output allows the script to terminate normally and the final achievement value is no less than $a_s$, you get $s$ points. If multiple conditions are met, the highest score is taken.
Formally, let $v_1$ be the final value of variable $1$ in your scheme. When your output is valid, your score is given by the table below:
| Score | Condition | Score | Condition |
|---|---|---|---|
| 10 | $v_1 \geq a_{10}$ | 5 | $a_5 \leq v_1 < a_6$ |
| 9 | $a_9 \leq v_1 < a_{10}$ | 4 | $a_4 \leq v_1 < a_5$ |
| 8 | $a_8 \leq v_1 < a_9$ | 3 | $a_3 \leq v_1 < a_4$ |
| 7 | $a_7 \leq v_1 < a_8$ | 2 | $0 < v_1 < a_3$ |
| 6 | $a_6 \leq v_1 < a_7$ | 1 | $v_1 \leq 0$ |
Implementation Details
We provide a tool called checker to test whether your output file is acceptable. To use this tool, run the following in the terminal:
./checker_linux64 <case_no>
where case_no is the number of the test data. For example:
./checker_linux64 3
will test if the corresponding output is acceptable.
If Linux users find they cannot run the program, please try executing chmod +x checker_linux64 or chmod +x checker_linux32 and try again.
The checker can also check the test results of any input and output files by running the following in the terminal:
./checker_linux64 <input_filename> <output_file_name>
where input_file_name and output_file_name are the names of the input and output files, respectively.
Use -w to output the results of each step. The usage is:
./checker_linux64 -w <input_file_name> <output_file_name>
or
./checker_linux64 -w <case_no>