With the development of human computer technology, the ever-increasing power of computers has made the Flea King very envious. Finally, one day, the Flea King issued a decree: vigorously develop the computer industry of the Flea Kingdom!
However, the Flea Kingdom has not yet undergone an industrial revolution and cannot manufacture the components required for electronic computers. But the Flea King came up with a brilliant idea: treat each flea as a computing node, with each flea performing only one specific small task.
The Flea King led $n$ fleas to a wilderness, arranged them as computing nodes in the field, and numbered them from $1$ to $n$. Each computing node takes the results of several (possibly zero) other computing nodes as input and calculates an output. In addition, the Flea King has a giant terminal that can input and output data; this terminal and all the computing nodes together form a computer.
Let the output of the $t$-th computing node be $x_t$. The operations of this node can be classified into the following types:
| Name | Operator (Type) | Operands | Calculation Result |
|---|---|---|---|
| Input Node | I | None | Read a real number from the terminal as $x_t$ |
| Output Node | O | $i$ | $x_t = x_i$, and output $x_t$ to the terminal |
| Addition Node | + | $i, j$ | $x_t = x_i + x_j$ |
| Offset Node | C | $i, c$ | $x_t = x_i + c$ |
| Negation Node | - | $i$ | $x_t = -x_i$ |
| Left Shift Node | < | $i, k$ | $x_t = x_i \cdot 2^k$ |
| Right Shift Node | > | $i, k$ | $x_t = x_i / 2^k$ |
| S-type Node | S | $i$ | $x_t = s(x_i)$ |
| Comparison Node | P | $i, j$ | $x_t = \begin{cases} -1 & x_i < x_j \\ 0 & x_i = x_j \\ 1 & x_i > x_j \end{cases}$ |
| Max Node | M | $i, j$ | $x_t = \begin{cases} x_i & x_i > x_j \\ x_j & x_i \le x_j \end{cases}$ |
| Multiplication Node | * | $i, j$ | $x_t = x_i \cdot x_j$ |
Where $s(x)$ is defined as follows: ($e$ is the natural constant, approximately $2.718281828459045 \dots$)
$$s(x) = \frac{1}{1 + e^{-x}}$$
The function graph of $s(x)$ is shown below:
The operands $i, j$ in the table above must all be less than the current node's number $t$. Thus, at the Flea King's command, the fleas can obtain inputs and calculate outputs in order from smallest to largest index. Each flea's computing power is limited; they can only be precise to 90 decimal places, and any excess will be rounded. Similarly, the decimal part of the operand $c$ in the table above cannot exceed 90 places. Additionally, the operand $k$ in the Left Shift and Right Shift nodes must be a non-negative integer and cannot exceed $10000$.
After arranging the fleas, the ambitious Flea King decided to test the computing power of this computer made of fleas. The Minister of Grasshoppers presented 10 computing tasks to the Flea King. Completing each task requires obtaining input from the terminal, performing intermediate calculations, and then outputting the result using an output node. The specific tasks are described as follows:
| ID | Input | Input Constraints | Output | ||||
|---|---|---|---|---|---|---|---|
| 1 | $a, b$ | $ | a | , | b | \le 10^9$, decimal part $\le 9$ places | $-2a - 2b$ |
| 2 | $a$ | $ | a | \le 10^9$, decimal part $\le 9$ places | $\frac{1}{1 + e^{17a}}$ | ||
| 3 | $a$ | $ | a | \le 10^9$, decimal part $\le 9$ places | $\begin{cases} -1 & a < 0 \\ 0 & a = 0 \\ 1 & a > 0 \end{cases}$ | ||
| 4 | $a$ | $ | a | \le 10^9$, decimal part $\le 9$ places | $ | a | $, the absolute value of $a$ |
| 5 | $a_1, \dots, a_{32}$ | $a_1, \dots, a_{32} \in \{0, 1\}$ | Treat $a_1, \dots, a_{32}$ as a binary integer (high bit left, low bit right), output its value | ||||
| 6 | $a$ | $0 \le a < 2^{32}$, $a$ is an integer | Output 32 integers, the binary representation of $a$ from high to low (pad with 0 if $< 32$ bits) | ||||
| 7 | $a, b$ | $0 \le a, b < 2^{32}$, $a, b$ are integers | The result of $a$ XOR $b$ | ||||
| 8 | $a$ | $ | a | \le 10^9$, decimal part $\le 9$ places | $\frac{a}{10}$ | ||
| 9 | $a_1, \dots, a_{16}$ | $ | a_1 | , \dots, | a_{16} | \le 10^9$, decimal part $\le 9$ places | Output 16 real numbers, the sorted result of $a_1, \dots, a_{16}$ |
| 10 | $a, b, m$ | $0 \le a, b < 2^{32}, 1 \le m < 2^{32}$, $a, b, m$ are integers | $a \cdot b \pmod m$ |
The Flea King realized he did not have the ability to design such a computer, so he found you, a participant in NOI. Please design the type and operands for each computing node in order to complete these 10 tasks, using as few computing nodes as possible.
Input
The input files nodes1.in~nodes10.in are in the problem directory, corresponding to the 10 computing tasks. Each input file contains only one integer, representing the ID of the task to be solved.
Output
The output files are nodes1.out~nodes10.out, corresponding to the input files. For each task, you need to output several lines, where the $i$-th line describes the $i$-th computing node. When describing each node, first provide a character representing the node type, followed by the parameters in order. Separate characters and numbers with spaces. The number of lines in the output must not exceed $10^4$.
Examples
Input 1
1
Output 1
I + 1 1 - 2 I + 4 4 - 5 + 3 6 - 7 - 8 O 9
Note
The example output is one possible construction for the first task. It uses 10 computing nodes and earns 3 points.
Subtasks
We provide ten grading files nodes1.ans~nodes10.ans, corresponding to each task. Each file contains 10 lines, with the $i$-th line containing a grading parameter $w_i$. Each test case is graded individually, with 10 points per case. If the output format is invalid or parameters do not meet the requirements, the score is 0.
Otherwise, the output is judged as follows: The grader generates several sets of input data and feeds them into your constructed computer. If, for any set of input data, the absolute value of the result of any computing node exceeds $10^{1000}$, you get 0 points. If any value in your output differs from the expected output by more than $10^{-9}$, your output is considered incorrect and you get 0 points.
Otherwise, your computer is considered capable of completing the task, and you are scored based on the following rules. Assuming a total of $n$ computing nodes are used, your score is given by the table below:
| Score | Condition | Score | Condition |
|---|---|---|---|
| 10 | $n \le w_{10}$ | 5 | $n \le w_5$ |
| 9 | $n \le w_9$ | 4 | $n \le w_4$ |
| 8 | $n \le w_8$ | 3 | $n \le w_3$ |
| 7 | $n \le w_7$ | 2 | $n \le w_2$ |
| 6 | $n \le w_6$ | 1 | $n \le w_1$ |
If none of the conditions are met, you get 0 points. If multiple conditions are met, you receive the highest score.
Additionally, the use of Comparison nodes, Max nodes, and Multiplication nodes is extremely expensive. Using any one of these types will deduct 4 points from your score for that test case. Note that this deduction is based on the number of types of nodes used, not the number of times they are used. For example, using a Comparison node multiple times only deducts 4 points; using both a Comparison node and a Multiplication node deducts 8 points. A test case score will not drop below 0.
Interaction
Switch to the problem directory in the terminal:
cd nodes
We provide a tool named checker to test your output. Run it as follows:
./checker <case_no>
where <case_no> is the test case number. For example:
./checker 3
The checker will provide the test results, including:
1. Abnormal exit: Unknown error.
2. Input file error: Contains error information.
3. Output error: Error information.
4. The total number of nodes is n. score: x: Output is acceptable, you used $n$ nodes, and your score for this test case is $x$.
You can also use the command ./checker -f <file_name> to run the computer represented by <file_name> and interact via the terminal. Note that the data used by checker when testing your computer may differ from the data used in the final evaluation.
Note
Please keep the input files nodes1.in~nodes10.in, grading files nodes1.ans~nodes10.ans, and output files nodes1.out~nodes10.out safe and backed up. Scores obtained by modifying input or grading files are invalid.