This is an interactive problem.

"You have ten thousand reasons to be different from your team's style.

"The simplest reason: you're too weak.

"Hahahahahaha."

$\mathfrak{rehtien}$ and $\mathfrak{airrats}$ are playing a number-guessing game.

The rules are as follows: $\mathfrak{rehtien}$ first thinks of a number $x$, and then $\mathfrak{airrats}$ makes a guess. If she guesses correctly, $\mathfrak{rehtien}$ will help her create problems.

But soon, $\mathfrak{airrats}$ realized the problem: "You won't even let me use binary search, how am I supposed to guess?" Therefore, $\mathfrak{airrats}$ stipulated that $|x|=1$, so she has a $\frac{1}{2}$ probability of guessing correctly.

However, after the next round of the game, $\mathfrak{rehtien}$ told her that $x\in \mathbb{C}$, and the number he thought of was $i$. $\mathfrak{airrats}$ was very angry. She felt it was necessary to use some mysterious methods.

Task Introduction

Specifically, $\mathfrak{airrats}$ has an array of length $2^n$, with $a_0=1$ initially and all other elements being 0.

She needs to implement a function SOL(t), where $t$ is the subtask number. The function returns a complex number representing $x$.

She can call the following functions:

INI(n), where $1\le n\le 16$. This function must be called exactly once before calling any of the functions below, and it initializes an array of length $2^n$.

CU(d,k), where $0\le d\lt n$ and $-2^{16}\lt k \lt 2^{16}$. After calling this function, for all $i$ whose $d$-th binary bit is 1, let $a'_i = x^k a_i$. Then $a_i$ is updated to $a'_i$.

CR(d1,d2,A), where $0\le d_1,d_2 \lt n$, and $A$ is a $2\times 2$ complex matrix satisfying $AA^*=I$, where $I$ is the identity matrix and $A^*$ is the conjugate transpose of $A$. After calling this function, for all $i$ where both the $d_1$-th and $d_2$-th binary bits are 1, let:

$$ \begin{equation} \left\{ \begin{array}{lr} a'_{i-2^{d_2}} = A_{0,0}a_{i-2^{d_2}}+A_{1,0}a_{i} \\ a'_{i}=A_{0,1}a_{i-2^{d_2}}+A_{1,1}a_{i} \end{array} \right.\end{equation} $$

Then $a_{i-2^{d_2}}$ is updated to $a'_{i-2^{d_2}}$, and $a_{i}$ is updated to $a'_{i}$.

ACR(A), where $A$ points to a $2^n\times 2^n$ complex matrix satisfying $AA^*=I$. After calling this function, let $a'_i=\sum_{j=0}^{2^n-1} A_{i,j}a_j$, then $a_i$ is updated to $a'_i$. If you need to call this function, please pay attention to the time and space complexity.

QR() returns a random integer in $[0, 2^n)$, where the probability of returning $i$ is $\frac{|a_i|^2}{\sum_{j} |a_j|^2}$.

Implementation Details

The source code must include the header file unnamable.h.

The function interfaces are as follows:

complex<double> SOL(int t);
void INI(int n);
void CU(int d,int k);
void CR(int d1,int d2,complex<double> A[2][2]);
void ACR(complex<double> **A);
int QR();

See the sample program sample.cpp for details. For the specific implementation of the above functions, see grader.cpp.

The provided grader will read three integers $ans, seed, typ$ from input.txt, representing the answer for the current test case, the random seed, and the subtask number, respectively, where $ans$ indicates $x=\omega_{65536}^{ans}$. After execution, the results and error messages will be output to result.txt.

Constraints

In each test case, SOL() will be called once. Let $res$ be the return value of SOL(). The result is considered correct if $|res-x|\le 10^{-5}$.

For all test cases, the total number of calls to CU, CR, QR, and ACR cannot exceed 300.

Here $\omega_n$ denotes the $n$-th root of unity, and $k$ is an integer.

A matrix satisfying $AA^*=I$ is called a unitary matrix.

The contestant's program and the interaction library share the time and space limits of this problem, but due to the existence of the ACR operation, we cannot guarantee the running time of the interaction library. The interaction library used for final evaluation (only guarantees) has the same implementation as the provided grader; please calculate the actual running time and memory usage yourself.