This is an interactive problem. Have fun!

There are $N$ people, labeled $0, 1, \ldots, N-1$, standing in a circle facing inward in counter-clockwise order. They play several rounds of a game. In each round, everyone wears a hat that is either black or white. Each person can see the hat colors of everyone else and, in the simple mode, knows their own label. After observing, everyone must simultaneously guess the color of their own hat. You need to design a deterministic strategy to maximize the number of people who guess correctly.

Specifically, your strategy is a function $f(a_0, a_1, \ldots, a_{N-2}, x)$. Here, $a_i \in \{0, 1\}$ represents the hat color of the person $i+1$ positions to the right (where $0$ is white and $1$ is black). In simple mode, $x$ is the person's label; otherwise, $x = -1$. The function returns $0$ or $1$, representing the person's guess for their own hat color.

In a round of the game, if the hat color of person $i$ is $b_i \in \{0, 1\}$, your strategy results in $\sum_{i=0}^{N-1}(1-|f(b_{(i+1)\bmod N}, b_{(i+2)\bmod N}, \ldots, b_{(i+N-1)\bmod N}, x_i)-b_i|)$ people guessing their own hat color correctly. Here, $x_i = i$ in simple mode, and $x_i = -1$ otherwise.

Implementation Details

Ensure that your program begins with #include "tmp.h". 'tmp' is short for 'the miaomiao problem'.

You do not need to, and should not, implement a main function. You must implement the following functions:

void init (int N, bool Type, int p);

This function is called exactly once at the beginning of each test case to provide information about the test case: + $N$ is the number of people. + $Type$ indicates whether it is simple mode ($1$ for yes, $0$ for no). + $p$ is the scoring parameter (see Constraints and Scoring).

bool guess (unsigned long long A, int x);

This function represents your strategy $f$ described above. unsigned long long A is the bit-packed representation of $a_0, a_1, \ldots, a_{N-2}$. You can obtain the actual $a_i$ ($0 \le i \le N-2$) using the expression ((A>>i)&1). The return value is $f(a_0, a_1, \ldots, a_{N-2}, x)$.

During final testing, for each test case, the interactor calls init exactly once. It then identifies the required $f(a_0, a_1, \ldots, a_{N-2}, x)$ for that test case and calls guess in an arbitrary order to obtain the values of $f$. You may refer to the provided sample interactor for more implementation details.

Testing Your Program

The problem files include a reference implementation of the interactor, grader.cpp, and the required header file tmp.h. The interactor used for final testing differs from this one only in random seeds and anti-cheating mechanisms.

You can place your tmp.cpp, grader.cpp, and tmp.h in the same directory and compile them using g++ tmp.cpp grader.cpp to generate an executable.

The executable runs as follows: + It reads the following data from standard input: + The first line contains three integers $N, Type, p$, representing the number of people, whether it is simple mode, and the scoring parameter. + The second line contains an integer $T$, the number of rounds played. + The next $T$ lines each contain an integer $B$, the bit-packed representation of the hat colors $b_0, b_1, \ldots, b_{N-1}$ for that round. You can obtain the actual $b_i$ ($0 \le i \le N-1$) using the expression ((B>>i)&1). + After reading, the interactor performs the test. If no runtime error occurs, it outputs: + The first line contains an integer representing the $p$-th smallest number of correct guesses across all $T$ rounds. + The second line contains a floating-point number representing the ratio of your score to the total possible score for that test case.

Constraints

There are $26$ test cases, which are not equally weighted.

For each test case: + Time limit: 4 seconds, Memory limit: 1 GiB. + The interactor uses at most 1 second and 256 MiB. + $3 \le N \le 64, Type \in \{0, 1\}, 1 \le p \le T, T=2^{\min\{N, 16\}}, 0 \le B < 2^N$.

The specific limits and scores for each test case are as follows:

For test cases where $p > 1$, $B$ is guaranteed to be generated uniformly at random from all integers in $[0, 2^N)$.

Each test case offers partial credit. For a test case with total score $P$, let $x$ be the $p$-th smallest number of correct guesses across all $T$ rounds. If $x=0$, your score for this test case is $0$. Otherwise, let $k$ be the smallest integer $>1$ such that $x \ge \lfloor \frac{N-1}{k} \rfloor$. Your score for this test case is $\frac{P}{(k-1)^{1.5}}$ (without rounding).