你被放置在一个长度未知的神秘环形通道中，通道由 $n$ 盏排成圆环的魔法灯组成。每盏灯要么是亮的，要么是灭的，但你不知道 $n$ 的值、你的起始位置，也不了解灯的初始状态。

你的任务是通过执行一系列交互操作来确定 $n$ 的值（圆环中灯的总数）。你可以使用四种操作：

• clockwise()：顺时针移动到下一盏灯。花费 1 美元。
• anticlockwise()：逆时针移动到上一盏灯。花费 1 美元。
• ask()：查询当前灯的状态。如果亮则返回 true，灭则返回 false。花费 1 美元。
• flip()：切换当前灯的状态（亮 $\leftrightarrow$ 灭）。此操作免费（花费 0 美元）。

在每次调用 solve 函数时，你最多可以使用 $2 \times 10^6$ 次操作。你的程序必须高效地确定 $n$ 的值。根据你消耗的总美元数，你的性能得分可能会有所不同。

实现细节

你必须实现以下函数：

int solve(int c);

• c 是子任务 ID（用于评分）。
• 该函数必须返回 $n$ 的值，即环形通道的长度。

你可以使用以下交互函数：

void clockwise();       // 顺时针移动到下一盏灯，花费 1 美元。
void anticlockwise();   // 逆时针移动到上一盏灯，花费 1 美元。
bool ask();             // 查询当前灯的状态，返回 true（亮）或 false（灭），花费 1 美元。
void flip();            // 切换当前灯的状态，花费 0 美元。

你不得实现 main() 函数。请包含提供的头文件：

#include "lane.h"

说明

• 在单个测试用例中，solve 函数可能会被多次调用。
• 交互是自适应的：评测系统可能会动态改变 $n$ 的值和灯的状态，只要这不与之前的 ask() 结果相矛盾。

样例评测程序

评测程序的样例实现可以在附件中找到。它可能与我们评测你提交代码时使用的实际评测系统有所不同。

你可以使用以下编译命令来编译你的程序：

g++ grader.cpp lane.cpp -o lane -O2 -std=c++14 -static

你也可以添加 -DDEBUG 来启用调试模式：

g++ grader.cpp lane.cpp -o lane -O2 -std=c++14 -static -DDEBUG

对于编译后的程序：

• 评测程序将从标准输入读取测试数据：
  • 输入的第一行包含两个整数 $c$ 和 $T$，分别表示子任务 ID 和测试用例的数量。
  • 对于每个测试用例，输入包含两行：
    • 第一行包含一个整数 $n$。
    • 第二行包含一个长度为 $n$ 的字符串，由 0 或 1 组成，表示顺时针方向上的初始状态（0 表示灭，1 表示亮）。
• 对于每个测试用例，评测程序将调用一次 solve 进行测试。测试结束后，评测程序将输出以下信息：
  • 第一行显示你的评分信息。
  • 第二行显示关于你测试的评价。
• 当开启调试模式时，评测程序会为每个测试用例将详细信息输出到 stderr。请确保在启用调试模式时输入数据不要过大。

样例

输入格式 1

2 1
2
01

输出格式 1

2

说明

假设 $n = 2$，初始灯的状态为 $[0, 1]$。以下是一个合法的交互过程：

问题附件

该问题包含以下文件：

1. grader.cpp：交互库的样例实现。
2. lane.h：必需的头文件（无需修改或查看）。
3. template_lane.cpp：帮助你入门的模板代码。
4. lane1.in, lane2.in, lane3.in：大型样例数据，每个子任务对应一个。

子任务

设总探索次数（调用 solve 的次数）为 $T$，设所有探索中通道长度之和为 $\sum n$。

保证：$1 \leq n \leq 10^5$，$1 \leq T \leq 10^6$，$\sum n \leq 10^7$。

子任务 1（3 分）

• $T \leq 10$。
• 所有灯初始均为灭。
• 对于每个测试用例，如果你使用最多 $2 \times 10^6$ 次操作正确确定了 $n$，则获得满分；否则得零分。

子任务 2（40 分）

• $n \leq 2\,000$，$T \leq 5\,000$。
• 对于每个测试用例，你必须使用最多 $20n$ 次操作，否则得零分。
• 设 $x$ 为一个测试用例中所有 $T$ 次探索中 $q/n$ 的最大值，其中 $q$ 为单次探索消耗的体力。该测试用例的得分为：
  • 若 $x \leq 7.83$，得 40 分。
  • 若 $x > 15$，得 0 分。
  • 若 $7.83 < x \leq 15$，得 $40 \times \frac{15 - x}{15 - 7.83}$ 分。

子任务 3（57 分）

• 无额外限制。
• 对于每个测试用例，你必须使用最多 $20n$ 次操作，否则得零分。
• 对于每次探索，设 $q$ 为消耗的体力，$n$ 为通道长度：
  • 若 $n \leq 2\,000$，满意度为 $\frac{q}{2n}$。
  • 若 $n > 2\,000$，满意度为 $\frac{q}{n}$。
• 设 $x$ 为一个测试用例中所有 $T$ 次探索中的最大满意度。该测试用例的得分为：
  • 若 $x \leq 5.35$，得 57 分。
  • 若 $x > 8$，得 0 分。
  • 若 $5.35 < x \leq 8$，得 $57 \times \frac{8 - x}{8 - 5.35}$ 分。