题目背景

这是一道函数式交互题。本题仅支持 C++ 提交。（出于某些原因，请不要使用 GCC 9 提交）

本地编译、提交时请在程序里加入以下函数声明语句：

int query(int, int);

任何在赛时攻击交互库而得分的行为均视为作弊。

题目描述

有一个长为 $n=2^k$ 的序列，基于这个序列建立了一棵线段树。现在线段树上有恰好一个节点被标记了。

你可以进行若干次询问，每次询问给定一个区间 $[l,r]$，交互库会在被修改的线段树上进行一次区间查询，你可以得知在被修改的线段树上这个区间对应的所有节点中，是否有节点被标记。

你需要在尽可能少的询问内找到这个节点。具体而言，若最优策略在最坏情况下需要 $Q$ 次询问，则你最多可以使用 $Q$ 次询问。

交互流程

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

std::pair<int, int> solve(int k);

该函数需要在得到答案后返回一个数对 $(x,y)$，表示被标记的线段树节点所对应的区间为 $[x,y]$。

你可以调用交互库提供的方法：

int query(int l, int r);

传入的 l 和 r 代表询问的区间为 $[l,r]$。交互库会返回对应的结果。你需要保证 $1\le l\le r\le n$。具体而言：

• 当没有节点被标记时，交互库返回 $0$；
• 当有节点被标记时，交互库返回 $1$；
• 当询问的区间不合法时，交互库会返回 $-1$，此时你需要立即结束这组数据的交互（不是整个测试点），否则可能导致不可预知的错误。

本题无询问次数限制，但过多的询问会导致时间超限，详细信息请看“数据规模与约定”。

输入格式

下面给出样例交互库的输入输出格式：

第一行输入一个整数 $T$，表示数据组数。

对于每组数据，第一行输入三个整数 $k,l,r$ 代表 $n=2^k$，且将对应区间为 $[l,r]$ 的线段树节点修改。

注意样例交互库不会检查输入数据的正确性。

输出格式

对于每组数据，如果你得到的答案正确，输出一个整数表示你使用的交互次数，否则：

• 若你的询问不合法，输出 Wrong Answer [1]；
• 若你返回的区间不正确，输出 Wrong Answer [2]。

2
2 1 1
2 3 4

1
2

提示

样例 1 解释

下面是一种可能的交互流程：

交互库	选手程序	备注
调用 solve(2)		开始测试
返回 $1$	调用 query(1,1)	$[1,1]$ 就是答案节点
	返回 $(1,1)$	答案正确
调用 solve(2)		开始下一组数据的评测
返回 $1$	调用 query(2,4)	$[2,4]$ 对应的节点是 $[2,2]$ 和 $[3,4]$，包括了答案节点
返回 $0$	调用 query(1,4)	$[1,4]$ 对应的节点只有 $[1,4]$，不包括答案节点
	返回 $(3,4)$	答案正确，评测结束

计分方式

本题首先会受到和传统题相同的限制。例如编译错误会导致整道题目得 $0$ 分，运行时错误、超过时间限制、超过空间限制等会导致相应测试点得 $0$ 分等。

如果你找到的节点是错误的，或者你给出的询问不合法，在该测试点将会得到 $0$ 分。

否则，设在一组数据中，答案最坏需要 $x$ 次询问，而你使用了 $y$ 次询问，满分为 $t$，则这组数据的分数是 $t\times \min\left(1,\mathrm{e}^{-\frac{y}{x}+1}\right)$。

每个测试点取所有数据组中得分的最小值，向下保留两位小数。你的得分是所有测试点得分之和。

数据规模与约定

对于所有数据，保证 $1\le k\le 14$，$1\le T\le 300$。

本题共 $14$ 个测试点，对于第 $i$ 个测试点，保证 $k=i$。对于 $1\le k\le 4$ 的测试点，满分 $10$ 分。对于 $5\le k\le 14$ 的测试点，满分 $6$ 分。

保证在每组数据进行 $2n$ 次询问时，单个测试点内，交互库使用的时间不超过 0.6s，空间不超过 8MiB。

下发文件说明

下发文件中有一个可以通过样例的程序示例 sample.cpp，以及一个样例交互库 grader.cpp。假设你的答案文件为 answer.cpp，则可以使用如下命令将其编译成可执行文件 answer：

g++ grader.cpp answer.cpp -o answer -O2

实际评测时的交互库可能是自适应的，即被修改的节点可能不会在交互一开始时确定。