题目背景

あの日々は消えても

まだ梦は消えない

君よ歌ってくれ

仆に歌ってくれ

忘れない忘れないものも　ここにあるよと

——《旅人のうた》

纵然那段往日逝去，

梦想仍旧不会消逝。

请君高歌吧，

为我放声高歌吧。

无法忘记，无法忘记，因为这里仍有牵挂。

题目描述

这是一道交互题。

qtree 先生到一个精灵王国旅游。

这里面有 $N$ 个精灵，所有精灵大致分为两类：

• 精明精灵：永远能正确判断其他精灵是否为精明精灵

• 糊涂精灵：无法完全正确判断其他精灵的身份，会给出一个随机数。其中有 $\frac{x}{x+y}$ 的概率会判断是精明精灵，$\frac{y}{x+y}$ 的概率会判断是糊涂精灵。

而且，由于基因的特性，精明精灵的数量永远不小于糊涂精灵的数量。

但是 qtree 在王国里迷路了，所以他想找一个精明精灵带路，作为 qtree 最聪明的鹦鹉，就由你来帮他找吧！

不过，这个问题你似乎在哪里见过……

实现细节

选手不需要，也不应该实现 main 函数。

选手需要确保提交的程序包含头文件 smart.h，即在程序开头加入以下代码：

#include "smart.h"

选手需要在提交的程序源文件 smart.cpp 中实现以下两个函数：

void init(int c, int T);

• $c, T$ 分别表示测试点编号与测试数据组数。$c = 0$ 表示该测试点为样例。
• 对于每个测试点，该函数会在程序开始运行时被交互库调用恰好一次。

int smart(int N, int X,int Y);

• $N,X,Y$ 为题面所述的条件参数。
• 该函数需要返回一个整数，表示一个你认为的是精明精灵的精灵。
• 对于每个测试点，该函数会被交互库调用恰好 $t$ 次。

选手可以通过调用以下函数进行一次询问：

int query(int x, int y);

• $x,y$ 表示两个精灵的编号。选手需要保证 $1 \le x , y \le n$。
• 该函数会返回精灵 $x$ 对精灵 $y$ 的身份判断。如果 $x$ 认为 $y$ 是精明人就返回 $1$，否则返回 $0$。
• 选手需要保证交互库每次调用 smart 时，调用该函数的次数不超过 $2\times 10^5$。

注意：在任何情况下，最终测试时所用的交互库运行所需时间均不会超过 $1$ 秒，所用内存为固定大小，且均不超过 $512$ MiB。

测试程序方式

试题目录下的 grader.cpp 是交互库参考实现，最终测试时所用的交互库实现与该参考实现有所不同，因此选手的解法不应该依赖交互库实现。

选手可以在本题目录下使用如下命令编译得到可执行程序：

g++ grader.cpp smart.cpp -o smart -std=gnu++14 -O2 -static

对于编译得到的可执行程序：

• 可执行文件将从标准输入读入以下格式的数据：
  • 输入的第一行包含两个非负整数 $c, T$，分别表示测试点编号和测试数据组数。
  • 接下来依次为每组测试数据，对于每组测试数据，包含第一行三个非负整数 $N,X,Y$ 和第二行一个长度为 $N$ 的字符串，表示这些精灵的身份（$0$ 为糊涂精灵，$1$ 为精明精灵）。
• 可执行文件将输出以下格式的数据至标准输出：
  • 对于每组测试数据，输出的第一行字符串表示测试结果：
    • Correct 表示选手返回的结果正确；
    • Wrong answer 表示选手返回的结果错误或格式不合法。

样例 1

输入

0 3
4 1 1
0011
4 1 1
0111
4 1 1
1111

输出

Correct
Correct
Correct

样例 2

见选手目录下的 smart/smart2.in 与 smart/smart2.ans。

该样例满足测试点 $4 \sim 6$ 的约束条件。

样例 3

见选手目录下的 smart/smart3.in 与 smart/smart3.ans。

该样例满足测试点 $7 \sim 8$ 的约束条件。

下发文件说明

在本试题目录下：

1. grader.cpp 是提供的交互库参考实现。
2. smart.h 是头文件，选手不用关心具体内容。
3. template_smart.cpp 是提供的示例代码，选手可参考并实现自己的代码。

选手注意对所有下发文件做好备份。最终评测时只测试本试题目录下的 smart.cpp，对该程序以外文件的修改不会影响评测结果。

数据范围

对于所有测试数据，均有：

• $t = 10$；
• $2 \le n \le 10^6$；
• $1 \le x,y \le 10^3$
• 保证精明精灵的数量大于等于糊涂精灵的数量。

测试点编号	$n =$	特殊性质
$1 \sim 3$	$10$	无
$4 \sim 6$	$100$
$7, 8$	$10^4$	A
$9$		B
$10$		C
$11, 12$	$10^6$	A
$13 \sim 20$		无

• 特殊性质 A：保证测试数据在满足题目的限制下随机生成。
• 特殊性质 B：$x=1,y=1000$
• 特殊性质 C：$y=1,x=1000$

评分方式

注意：

• 选手不应当通过非法方式获取交互库的内部信息，如直接与标准输入、输出流进行交互。此类行为将被视为作弊；
• 最终的评测交互库与样例交互库的实现不同。

本题首先会受到和传统题相同的限制，例如编译错误会导致整道题目得 $0$ 分，运行时错误、超过时间限制、超过空间限制等会导致相应测试点得 $0$ 分等。选手只能在程序中访问自己定义的变量以及交互库给出的变量，尝试访问其他地址空间将可能导致编译错误或运行错误。

每次调用 smart 函数时，若返回的精灵是糊涂的，或 query 函数调用不合法，或 query 函数调用次数超过 $2\times 10^5$，则相应测试点得 $0$ 分。