题目描述

这是一道交互题。

某天，你在小明埋在地下的宝藏屋中探险。

小明的宝藏屋呈一个无限满二叉树的结构，其中根节点与地面相连，如下图所示：

不知怎么的，你突然迷路了。好在小明考虑到了这点，于是它在你探险之前给了你一个探测器，它能给你得到你离地面的相对高度 (即当前宝藏屋的深度，其中地面的深度为 $0$)，不过它的电量已经不足，因此至多只能使用 $T$ 次。

由于每个宝藏屋都有恰好 $3$ 条道路连接它，故小明为了方便起见，把与每个宝藏屋相邻的三条道路分别编号为 $0, 1, 2$。

目前你只知道你当前离地面的相对高度，你需要编写一套寻路系统来到达地面。注意你现在的食物和水分只够你移动 $1050000$ 次。

任务

你需要编写一个函数 explore，来模拟寻路的过程：

• explore(n, T):
  • n 表示你当前所在宝藏屋的深度。
  • T 表示你能使用探测器的次数上限。
  • 函数不需要返回值，当你到达地面时，请立即退出函数。

你可以调用两个函数 move 和 query 来完成寻路：

• move(type):
  • type 表示你所选的道路的编号。
  • 调用此函数后会从当前结点沿着编号为 type 的道路进行一次移动。
  • 函数返回一个 bool，表示移动后是否到达地面。
• query():
  • 函数返回一个 int，表示当前你离地面的相对高度。

实现细节

本题只支持 C++。

你只能提交一个源文件实现如上所述的 explore 函数，并且遵循下面的命名和接口。你需要包含头文件 explore.h。

void explore(int n, int T);

函数 move, query 的接口信息如下。

bool move(int type);
int query();

如果有不清楚的地方，见样例及测评库下载，内附了样例程序。

评测方式

评测系统将读入如下格式的输入数据：

第一行包含两个整数 $n, T$，意义同 explore 函数。

第二行包含一个长度为 $n$ 的仅由 $\texttt 0, \texttt 1, \texttt 2$ 组成的字符串，表示地面与你所在的宝藏屋的连线中，(从浅到深) 每条道路的编号，保证相邻两个字符不同。

如果 explore 正常返回且到达地面，评测系统将分别输出你调用 move 和 query 的次数，否则返回一条错误信息，有如下几种形式：

1. move: too many calls [more than 1050000] 调用 move 的次数超过 $1050000$；
2. move: already at the ground 已经到达地面却仍在调用 move 函数；
3. move: type [equals to x] not in [0, 2] 调用 move 的参数 type 等于 $x$，不为 $\{0, 1, 2\}$ 之一；
4. query: too many calls [more than T] 调用 query 的次数超过 $T$；
5. not escaped explore 返回后未到达地面。

3 1000
102

11 7

样例 2

见附加文件中的 ex_explore2.in 与 ex_explore2.out。

数据范围与提示

本题共 $10$ 个测试点，每个测试点 $10$ 分。每个测试点的 $n$ 和 $T$ 见下表：

测试点编号	$n$	$T$
1	$= 1000$	$= 2 \times 10^9$
2	$= 10^5$
3	$= 1000$	$= 2001$
4		$= 1024$
5	$= 10^5$	$= 200001$
6		$= 154000$
7		$= 103000$
8		$= 67000$
9		$= 51000$
10