This is an output-only task.

Description

While implementing a circuit for a robot, you notice some anomalies. There are $N = 128$ programs, numbered from $0$ to $N-1$, that the robot may run. Normally, only one program (out of the $N$ programs) should be running at any given moment. However, for some unknown reasons, sometimes exactly three programs run simultaneously. Fortunately, as an experienced programmer, you know how to handle this situation and decide to implement a circuit to detect such anomalies.

You first create $N$ inputs. The $i$-th input is $0$ if the $i$-th program is not running, and $1$ otherwise. Then, you add gates, which have indices numbered consecutively starting from $N$. Each gate can take a certain number of inputs and produce a single output, either $0$ or $1$. The inputs of the $i$-th gate can be the output of any gate with index less than $i$, or any of the initial $N$ inputs.

There are three types of gates:

• NOT: takes exactly one input. The output is $1$ if the input is $0$, and $0$ otherwise.
• OR: takes exactly two inputs. The output is $0$ if both inputs are $0$, and $1$ otherwise.
• AND: takes exactly two inputs. The output is $1$ if both inputs are $1$, and $0$ otherwise.

The output of the last gate should be $1$ if an anomaly is detected—that is, if exactly three of the first $N$ inputs are $1$—and $0$ if exactly one of the first $N$ inputs is $1$.

It is guaranteed that the number of $1$s among the first $N$ inputs is either exactly one or exactly three.

Implementation Details

You have to write to an output file describing a valid circuit for $\color{red}{N = 128}$.

The first line of the output should contain an integer representing the number of gates used.

Each line of the rest of the output should be one of the following three formats:

NOT in_1
OR in_1 in_2
AND in_1 in_2

Each one appends a NOT, OR or AND gate, respectively. For NOT, in_1 is the index of the input of the gate. For OR and AND, in_1 and in_2 are the indices of the inputs of the gate. The index of the gate appended in the $i$-th line after the first line is $N-1 + i$.

The total number of gates should not exceed $1024$. In other words, the total number of lines in the output file should not exceed $1025$.

Subtasks

1. (100 points) No additional constraints.

Scoring

For each subtask, if there exists a case that the circuit does not pass, your score will be $0$.

Otherwise, let $K$ denote the number of gates used by the circuit. Your score will be $f(K) \times$ [the score of the subtask], where:

$f(K) = \begin{cases} 0 & 1024 < K \\ 0.3 - 0.1 \times \frac {K - 384}{896} & 384 < K \le 1024 \\ 0.6 - 0.3 \times \frac {K - 256}{128} & 256 < K \le 384 \\ 1 - 0.40 \times \frac{K - 215}{41} & 215 < K \le 256 \\ 1 & K \le 215 \end{cases}$

Figure 1: The score for the task for each value of $K$

You have to write your solution in the output file 1.out, then compress the output files into a single.zip file and submit the.zip file.

Example

Consider a simplified version of the task with $N = 4$ (Note that you only need to provide the solution for $N = 128$). A possible solution is to build the following circuit.

3
OR 0 1
OR 2 3
AND 4 5

The circuit has:

• gate $4$ that outputs $1$ if at least one of input $0$ or $1$ is $1$;
• gate $5$ that outputs $1$ if at least one of input $2$ or $3$ is $1$; and
• gate $6$ that outputs $1$ if both the outputs of gate $4$ and gate $5$ is $1$.

One can check that for all possible inputs, the circuit gives the correct answer.