There is no input in this problem; your program only needs to output a solution.

Formally, the state of a single qubit $$$\vert\psi\rangle$$$ can be written as $$$\alpha\vert0\rangle+\beta\vert1\rangle$$$, where $$$\alpha,\beta$$$ are complex numbers satisfying $$$\vert\alpha\vert^2+\vert\beta\vert^2=1$$$. Here, we regard this purely as an abstract mathematical object and do not discuss its physical meaning.

If we measure $$$\vert\psi\rangle$$$:

• With probability $$$\vert\alpha\vert^2$$$ we obtain the result $$$0$$$ and $$$\vert\psi\rangle$$$ collapses to $$$\vert0\rangle$$$ (that is, $$$1\cdot\vert0\rangle+0\cdot\vert1\rangle$$$).
• With probability $$$\vert\beta\vert^2$$$ we obtain the result $$$1$$$ and $$$\vert\psi\rangle$$$ collapses to $$$\vert1\rangle$$$ (that is, $$$0\cdot\vert0\rangle+1\cdot\vert1\rangle$$$).

For multiple qubits, for example $$$\vert\psi_1\rangle=\alpha\vert0\rangle+\beta\vert1\rangle$$$ and $$$\vert\psi_2\rangle=\gamma\vert0\rangle+\delta\vert1\rangle$$$, the state of the composite system is $$$$$$ \begin{aligned} \vert\psi_1\rangle\vert\psi_2\rangle&=(\alpha\vert0\rangle+\beta\vert1\rangle)(\gamma\vert0\rangle+\delta\vert1\rangle)\\ &=\alpha\gamma\vert0\rangle\vert0\rangle+\alpha\delta\vert0\rangle\vert1\rangle+\beta\gamma\vert1\rangle\vert0\rangle+\beta\delta\vert1\rangle\vert1\rangle \end{aligned} $$$$$$ It is easy to see that $$$\vert\alpha\gamma\vert^2+\vert\alpha\delta\vert^2+\vert\beta\gamma\vert^2+\vert\beta\delta\vert^2=1$$$.

Different qubits are not always separable. Consider the general state of a two-qubit system $$$$$$ \vert\psi_1\rangle\vert\psi_2\rangle=\alpha_{00}\vert0\rangle\vert0\rangle+\alpha_{01}\vert0\rangle\vert1\rangle+\alpha_{10}\vert1\rangle\vert0\rangle+\alpha_{11}\vert1\rangle\vert1\rangle $$$$$$ where $$$\vert\alpha_{00}\vert^2+\vert\alpha_{01}\vert^2+\vert\alpha_{10}\vert^2+\vert\alpha_{11}\vert^2=1$$$. If this expression cannot be factorized as $$$(\alpha\vert0\rangle+\beta\vert1\rangle)(\gamma\vert0\rangle+\delta\vert1\rangle)$$$, then we say that $$$\vert\psi_1\rangle$$$ and $$$\vert\psi_2\rangle$$$ are in an entangled state. Once an entangled state is formed, the correlation between the two qubits persists even if they are separated far apart in space.

If we measure $$$\vert\psi_1\rangle$$$ in this system:

• With probability $$$\vert\alpha_{00}\vert^2+\vert\alpha_{01}\vert^2$$$ we obtain the result $$$0$$$ and $$$\vert\psi_1\rangle\vert\psi_2\rangle$$$ collapses to $$$\dfrac{\vert0\rangle(\alpha_{00}\vert0\rangle+\alpha_{01}\vert1\rangle)}{\sqrt{\vert\alpha_{00}\vert^2+\vert\alpha_{01}\vert^2}}$$$.
• With probability $$$\vert\alpha_{10}\vert^2+\vert\alpha_{11}\vert^2$$$ we obtain the result $$$1$$$ and $$$\vert\psi_1\rangle\vert\psi_2\rangle$$$ collapses to $$$\dfrac{\vert1\rangle(\alpha_{10}\vert0\rangle+\alpha_{11}\vert1\rangle)}{\sqrt{\vert\alpha_{10}\vert^2+\vert\alpha_{11}\vert^2}}$$$.

Measuring $$$\vert\psi_2\rangle$$$ in this system is similar. The roles of $$$\vert\psi_1\rangle$$$ and $$$\vert\psi_2\rangle$$$ are symmetric.

Quantum gates are basic tools for manipulating qubits.

In this problem, you may use, and are only allowed to use, the H gate, X gate, Z gate, and CNOT gate.

To apply an H, X, or Z gate, you must choose a target qubit $$$\vert\psi\rangle$$$. Suppose before the operation $$$\vert\psi\rangle=\alpha\vert0\rangle+\beta\vert1\rangle$$$, then:

• The H gate transforms it into $$$\vert\psi\rangle=\alpha\dfrac{\vert0\rangle+\vert1\rangle}{\sqrt2}+\beta\dfrac{\vert0\rangle-\vert1\rangle}{\sqrt2}$$$.
• The X gate transforms it into $$$\vert\psi\rangle=\alpha\vert1\rangle+\beta\vert0\rangle$$$.
• The Z gate transforms it into $$$\vert\psi\rangle=\alpha\vert0\rangle-\beta\vert1\rangle$$$.

To apply a CNOT gate, you must choose a control qubit $$$\vert\psi_1\rangle$$$ and a target qubit $$$\vert\psi_2\rangle$$$, which cannot be the same qubit. Suppose before the operation $$$$$$ \vert\psi_1\rangle\vert\psi_2\rangle=\alpha_{00}\vert0\rangle\vert0\rangle+\alpha_{01}\vert0\rangle\vert1\rangle+\alpha_{10}\vert1\rangle\vert0\rangle+\alpha_{11}\vert1\rangle\vert1\rangle $$$$$$ then the CNOT gate transforms it into $$$$$$ \vert\psi_1\rangle\vert\psi_2\rangle=\alpha_{00}\vert0\rangle\vert0\rangle+\alpha_{01}\vert0\rangle\vert1\rangle+\alpha_{10}\vert1\rangle\vert1\rangle+\alpha_{11}\vert1\rangle\vert0\rangle $$$$$$ Note that when applying quantum gates, we do not impose any restriction on how the involved qubits may be entangled with other qubits. For example, suppose $$$$$$ \vert\psi_1\rangle\vert\psi_2\rangle\vert\psi_3\rangle=\vert0\rangle\vert0\rangle\vert1\rangle+\vert1\rangle\vert1\rangle\vert0\rangle $$$$$$ If we apply a CNOT gate with $$$\vert\psi_3\rangle$$$ as the control qubit and $$$\vert\psi_1\rangle$$$ as the target qubit, then the resulting state is $$$$$$ \vert\psi_1\rangle\vert\psi_2\rangle\vert\psi_3\rangle=\vert1\rangle\vert0\rangle\vert1\rangle+\vert1\rangle\vert1\rangle\vert0\rangle $$$$$$ After learning some basic knowledge, Little L wonders: What does this all mean (He yi wei)?

So he designs the $$$\mathcal{HYW}$$$ language — an extremely simple quantum programming language.

A $$$\mathcal{HYW}$$$ program consists of several statements, one per line. The interpreter executes the statements in order from top to bottom.

Statements are divided into measurement statements and operation statements.

A measurement statement has the form $$$\texttt{measure }x$$$, which means to measure $$$\vert\psi_x\rangle$$$. The measurement result is either $$$0$$$ or $$$1$$$.

An operation statement must be one of the following two types:

Format	Meaning
$$$\texttt{ \lt statement \gt }$$$	Execute <statement>
$$$\texttt{if \lt condition \gt then \lt statement \gt }$$$	If <condition> is true, execute <statement>

Here, <statement> must be one of the following four types:

Format	Meaning
$$$\texttt{H }x$$$	Apply an H gate to the target qubit $$$\vert\psi_x\rangle$$$
$$$\texttt{X }x$$$	Apply an X gate to the target qubit $$$\vert\psi_x\rangle$$$
$$$\texttt{Z }x$$$	Apply a Z gate to the target qubit $$$\vert\psi_x\rangle$$$
$$$\texttt{CNOT }x\texttt{ }y$$$	Apply a CNOT gate with control qubit $$$\vert\psi_x\rangle$$$ and target qubit $$$\vert\psi_y\rangle$$$

<condition> has the form $$$\texttt{m}x\texttt{=}y$$$, meaning "the result of the $$$x$$$-th measurement (measure) is $$$y$$$".

For example, suppose initially $$$\vert\psi_1\rangle\vert\psi_2\rangle=\vert0\rangle\vert0\rangle$$$. To make $$$\vert\psi_1\rangle\vert\psi_2\rangle=\dfrac{\vert0\rangle\vert0\rangle+\vert1\rangle\vert1\rangle}{\sqrt2}$$$, a $$$\mathcal{HYW}$$$ program can be:

H 1
CNOT 1 2

After each statement is executed, the state evolves as follows:

1. $$$\vert\psi_1\rangle\vert\psi_2\rangle=\dfrac{\vert0\rangle+\vert1\rangle}{\sqrt2}\vert0\rangle$$$.
2. $$$\vert\psi_1\rangle\vert\psi_2\rangle=\dfrac{\vert0\rangle\vert0\rangle+\vert1\rangle\vert1\rangle}{\sqrt2}$$$.

Then, in order to turn $$$\vert\psi_1\rangle\vert\psi_2\rangle$$$ back into $$$\vert0\rangle\vert0\rangle$$$, a $$$\mathcal{HYW}$$$ program can be:

measure 1
if m1=1 then X 1
if m1=1 then X 2

After each statement is executed, the state evolves as follows:

1. It may be $$$\vert\psi_1\rangle\vert\psi_2\rangle=\vert0\rangle\vert0\rangle$$$ (if the measurement result is $$$0$$$), or it may be $$$\vert\psi_1\rangle\vert\psi_2\rangle=\vert1\rangle\vert1\rangle$$$ (if the measurement result is $$$1$$$).
2. It may be $$$\vert\psi_1\rangle\vert\psi_2\rangle=\vert0\rangle\vert0\rangle$$$, or it may be $$$\vert\psi_1\rangle\vert\psi_2\rangle=\vert0\rangle\vert1\rangle$$$.
3. $$$\vert\psi_1\rangle\vert\psi_2\rangle=\vert0\rangle\vert0\rangle$$$.

Now, consider the following task:

Initially, $$$\vert\psi_1\rangle=\alpha\vert0\rangle+\beta\vert1\rangle$$$, $$$\vert\psi_2\rangle=\vert0\rangle$$$, and $$$\vert\psi_3\rangle=\vert0\rangle$$$.

Your goal is to make $$$\vert\psi_1\rangle=\vert0\rangle$$$, $$$\vert\psi_2\rangle=\vert0\rangle$$$, and $$$\vert\psi_3\rangle=\alpha\vert0\rangle+\beta\vert1\rangle$$$.

You need to design a $$$\mathcal{HYW}$$$ program with at most $$$16$$$ statements to achieve this goal.

H 1
CNOT 1 2

#include <bits/stdc++.h>
int main() {
  puts("H 1");
  puts("CNOT 1 2");
  return 0;
}