You are placed in a mysterious circular lane of unknown length consisting of $n$ magical lamps, arranged in a ring. Each lamp is either on or off, but you have no knowledge of the value of $n$, your starting position, or the states of any lamps initially.

Your task is to determine the value of $n$, the total number of lamps arranged in the circle, by performing a series of interactive operations. You can use four types of operations:

• clockwise(): Move one step clockwise to the next lamp. Costs 1 dollar.
• anticlockwise(): Move one step counterclockwise to the previous lamp. Costs 1 dollar.
• ask(): Query the current lamp’s state. Returns true if on, false if off. Costs 1 dollar.
• flip(): Toggle the current lamp’s state (on ↔ off). This operation is free (costs 0 dollar).

You can use at most $2 \times 10^6$ operations in each invocation of your solve function. Your solution must determine the value of $n$ efficiently. Depending on the total dollar you consume, your performance score may vary.

Implementation Details

You must implement the following function:

int solve(int c);

• c is the subtask ID (used for scoring).
• The function must return the value of $n$, the length of the circular lane.

You are provided with the following interactive functions:

void clockwise();       // Move to next lamp (clockwise), costs 1 dollar.
void anticlockwise();   // Move to previous lamp (counterclockwise), costs 1 dollar.
bool ask();             // Query current lamp state, returns true (on) or false (off), costs 1 dollar.
void flip();            // Flip current lamp state, costs 0 dollar.

You must not implement main(). Include the provided header file with:

#include "lane.h"

Notes

• The function solve may be called multiple times during a single test case.
• The interaction is adaptive: the grader may dynamically change the value of $n$ and the lamp states, as long as it does not contradict previous ask() results.

Sample Grader

The sample implementation of the grader can be found in the attachments. It might differ from the actual grading system we used when judging your submission.

You may use the following compilation command to compile your program

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

You can also add the -DDEBUG to enable the Debugging Mode

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

For the compiled program:

• The grader will read the test data from the standard input:
  • The first line of the input contains two integers $c$ and $T$, indicating the subtask ID and the number of test cases.
  • For each test case, the input consists of two lines:
    • The first line of the input contains a single integer $n$.
    • The next line of the input contains a string with $n$ characters, each of 0 or 1, indicating the initial state (0 for off and 1 for on), in the clock-wise order.
• For each test case, the grader will call solve once for testing. After the testing, the grader will output the following information:
  • First line indicating your scoring information
  • Second line indicating the comments for your testing
• When Debugging Mode is on, the grader will output the details to stderr for each test case. Please make sure that your input is not huge when enabling the Debugging Mode.

Example

Suppose $n = 2$, and the initial lamp states are $[0, 1]$. The following is a valid interaction:

Problem Attachments

The problem includes the following files:

1. grader.cpp: A sample implementation of the interaction library.
2. lane.h: The required header file (no need to modify or inspect).
3. template_lane.cpp: Template code to help you get started.
4. lane1.in, lane2.in, lane3.in: Large sample cases, one for each subtask.

Subtasks

Let the total number of explorations (calls to solve) be $T$, and let $\sum n$ be the sum of all alley lengths over all explorations.

It is guaranteed that: $1 \leq n \leq 10^5$, $1 \leq T \leq 10^6$, $\sum n \leq 10^7$.

Subtask 1 (3 points)

• $T \leq 10$.
• All lamps are initially off.
• For each test case, you get full points if you use at most $2 \times 10^6$ operations to correctly determine $n$; otherwise, zero points.

Subtask 2 (40 points)

• $n \leq 2\,000$, $T \leq 5\,000$.
• For each test case, you must use at most $20n$ operations, otherwise zero points.
• Let $x$ be the maximum value of $q/n$ over all $T$ explorations in a test case, where $q$ is the stamina spent for one exploration. The score for the test case:
  • If $x \leq 7.83$, full 40 points.
  • If $x > 15$, zero points.
  • If $7.83 < x \leq 15$, you get $40 \times \frac{15 - x}{15 - 7.83}$ points.

Subtask 3 (57 points)

• No additional constraints.
• For each test case, you must use at most $20n$ operations, otherwise zero points.
• For each exploration, let $q$ be stamina spent, $n$ be the alley length:
  • If $n \leq 2\,000$, satisfaction is $\frac{q}{2n}$.
  • If $n > 2\,000$, satisfaction is $\frac{q}{n}$.
• Let $x$ be the maximum satisfaction among all $T$ explorations in a test case. The score for the test case:
  • If $x \leq 5.35$, full 57 points.
  • If $x > 8$, zero points.
  • If $5.35 < x \leq 8$, you get $57 \times \frac{8 - x}{8 - 5.35}$ points.