这是一道交互题，希望大家玩得开心 :)

有 $N$ 个人，标号分别为 $0,1,\ldots,N-1$，按逆时针顺序面对面地依次围成一个圈。他们会进行若干轮游戏，每轮游戏中每个人头上会佩戴一顶帽子，可能是黑色或白色的。每个人只能看到其他人的帽子颜色以及在简单模式下能得知自己的编号。所有人在进行观察后要同时猜测自己帽子的颜色，你要设计一个确定性的策略使得猜中的人数尽可能多。

具体地，你的策略是一个函数 $f(a_0,a_1,\ldots,a_{N-2},x)$。其中 $a_i\in\{0,1\}$ 代表一个人看到的右手边第 $i+1$ 个人的帽子颜色（$0$ 为白色，$1$ 为黑色，下同）。在简单模式下，$x$ 为这个人的编号，否则 $x=-1$。函数将要返回一个 $0$ 或 $1$ 代表这个人猜测的自己帽子的颜色。

在一轮游戏中，若第 $i$ 个人帽子颜色为 $b_i\in\{0,1\}$，那么你的策略能使 $\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|)$ 个人猜中自己帽子颜色。其中若在简单模式下，$x_i=i$，否则 $x_i=-1$。

实现细节

请确保你的程序开头有 #include "tmp.h"。'tmp' is short for 'the miaomiao problem'.

你不需要，也不应该实现主函数。你需要实现如下几个函数：

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

该函数将在每个测试点开始测试时恰好被调用一次，用来告诉你该测试点的一些信息。其中：

• $N$ 表示人数。
• $Type$ 表示是否为简单模式，若为 $1$ 则是，否则不是。
• $p$ 表示评分参数，具体见【数据范围与评分方式】。

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

该函数代表你给出的策略，即【题目描述】中的 $f$。其中 unsigned long long A 为 $a_0,a_1,\ldots,a_{N-2}$ 压位后的结果，你可以通过表达式 ((A>>i)&1) 来获得真实的 $a_i(0\le i\le N-2)$。该函数的返回值即为 $f(a_0,a_1,\ldots,a_{N-2},x)$。

最终测试时，对于每个测试点，交互库会恰好调用一次 init 函数。然后将该测试点中需要用到的 $f(a_0,a_1,\ldots,a_{N-2},x)$ 找出，并以任意顺序调用 guess 来得到每个 $f$ 的值。你可以查看参考交互库了解更多实现细节。

测试程序方式

本题下发文件中提供了一个交互库的参考实现 grader.cpp 和所需头文件 tmp.h。最终测试时所用的交互库实现与该实现仅有随机种子与反作弊上的不同。

你可以将自己的程序 tmp.cpp 与 grader.cpp 以及 tmp.h 放在同一目录下并通过命令 g++ tmp.cpp grader.cpp 来生成可执行文件。

该可执行文件运行方式如下：

• 可执行文件将从标准输入读入以下格式的数据：

  • 第一行三个整数 $N,Type,p$，分别表示人数，是否为简单模式以及评分参数。
  • 第二行一个整数 $T$ 表示该数据中进行的游戏轮数。
  • 接下来 $T$ 行每行一个整数 $B$ 表示每轮游戏里每个人的帽子颜色 $b_0,b_1,\ldots,b_{N-1}$ 的压位表示。你可以通过表达式 ((B>>i)&1) 来获得真实的 $b_i(0\le i\le N-1)$。

• 读入之后，交互库会进行测试。若没有出现运行时错误，则会输出：

  • 第一行一个整数，代表总共 $T$ 轮游戏中猜中人数的第 $p$ 小值。
  • 第二行一个浮点数，代表你的程序在该数据中的得分占该数据总分值的比值。

数据范围与评分方式

本题共有 $26$ 个测试点，测试点不等分。

对于每个测试点保证：

• 时间限制为 4 秒，空间限制为 1 GiB。
• 交互库所用时间不超过 1 秒，所用空间不超过 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$。

每个测试点的具体限制及分值如下：

同时，对于 $p > 1$ 的测试点，保证 $B$ 在所有 $[0,2^N)$ 间的整数中均匀随机生成。

每个测试点均有部分分，具体评分方式为：对于一个分数为 $P$ 的测试点，记你在该测试点中总共 $T$ 轮游戏里猜中人数的第 $p$ 小值为 $x$。那么若 $x=0$，则你在该测试点中得分为 $0$。否则，记 $k$ 为满足 $x\ge\left\lfloor{N-1\over k}\right\rfloor$ 的最小的 $>1$ 的整数，则你在该测试点中得分为 ${P\over (k-1)^{1.5}}$ （不进行取整）。