CF1924F.Anti-Proxy Attendance

This is an interactive problem!

Mr. 1048576 is one of those faculty who hates wasting his time in taking class attendance. Instead of taking attendance the old-fashioned way, he decided to try out something new today.

There are $n$ students in his class, having roll numbers $1$ to $n$. He knows that exactly $1$ student is absent today. In order to determine who is absent, he can ask some queries to the class. In each query, he can provide two integers $l$ and $r$ ($1\leq l\leq r\leq n$) and all students whose roll numbers are between $l$ and $r$ (inclusive) will raise their hands. He then counts them to determine if the roll number of the absent student lies between these values.

Things seemed fine until his teaching assistant noticed something — the students are dishonest! Some students whose roll numbers lie in the given range may not raise their hands, while some other students whose roll number does not lie in the given range may raise their hands. But the students don't want to raise much suspicion. So, only the following $4$ cases are possible for a particular query $(l,r)$ —

1. True Positive: $r-l+1$ students are present and $r-l+1$ students raised their hands.
2. True Negative: $r-l$ students are present and $r-l$ students raised their hands.
3. False Positive: $r-l$ students are present but $r-l+1$ students raised their hands.
4. False Negative: $r-l+1$ students are present but $r-l$ students raised their hands.

In the first two cases, the students are said to be answering honestly, while in the last two cases, the students are said to be answering dishonestly. The students can mutually decide upon their strategy, not known to Mr. 1048576. Also, the students do not want to raise any suspicion and at the same time, want to create a lot of confusion. So, their strategy always meets the following two conditions —

1. The students will never answer honestly $3$ times in a row.
2. The students will never answer dishonestly $3$ times in a row.

Mr. 1048576 is frustrated by this act of students. So, he is willing to mark at most $2$ students as absent (though he knows that only one is). The attendance is said to be successful if the student who is actually absent is among those two. Also, due to limited class time, he can only ask up to $\lceil\log_{1.116}{n}\rceil-1$ queries (weird numbers but okay). Help him complete a successful attendance.

Interaction

First read a line containing a single integer $t$ ($1\leq t\leq 2048$) denoting the number of independent test cases that you must solve.

For each test case, first read a line containing a single integer $n$ ($3\leq n\leq 10^5$). Then you may ask up to $\lceil\log_{1.116}{n}\rceil-1$ queries.

To ask a query, print a single line in the format "? l r" (without quotes) $(1\leq l\leq r\leq n)$. Then read a single line containing a single integer $x$ ($r-l\leq x\leq r-l+1$) denoting the number of students who raised their hands corresponding to the query.

To mark a student as absent, print a single line in the format "! a" (without quotes) $(1\leq a\leq n)$. Then read a single integer $y$ ($y\in{0,1}$). If the student with roll number $a$ was absent, $y=1$, else, $y=0$. Note that this operation does not count as a query but you can do this operation at most $2$ times.

To end a test case, print a single line in the format "#" (without quotes). Then you must continue solving the remaining test cases.

If you ask more queries than allowed or ask an invalid query, you will get the Wrong answer verdict.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

After printing the answers, do not forget to output end of line and flush the output buffer. Otherwise, you will get the verdict Idleness limit exceeded. To flush the buffer, use:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• flush(output) in Pascal;
• stdout.flush() in Python;
• Read documentation for other languages.

Note that the grader for this problem is adaptive meaning that the answer may change depending on your queries but will always remain consistent with the constraints and the answer to the previous queries.

Input format for Hacks

The test cases for this problem use both non-adaptive and adaptive graders. You can use the non-adaptive grader for making hacks.

The first line of input contains a single integer $t$ ($1\leq t\leq 2048$).

The first line of each test case contains three integers $g$, $n$ and $x$ where $g=1$ (to identify that this test case must use the non-adaptive grader), $n$ ($3\leq n\leq 10^5$) represents the number of students in the class and $x$ ($1\leq x\leq n$) represents the roll number of the student who is absent. You must ensure that the sum of $n$ over all test cases does not exceed $10^5$.

The second line of each test case contains a single string $S$ ($1\leq\vert S\vert\leq 120, S_i\in {\texttt{T},\texttt{F}}$). This string represents the pattern of the truth sequence. If $S_{(i-1)\bmod \vert S\vert+1}= \texttt{T}$, the students will act honestly during the $i$-th query, otherwise they will act dishonestly. You must also ensure that there is no index $i$ such that $S_{(i-1)\bmod \vert S\vert+1} = S_{i\bmod \vert S\vert+1} = S_{(i+1)\bmod \vert S\vert+1}$.

这是一个交互式问题！

1048576 老师是那种讨厌花时间点名的教师之一。他没有采用传统的点名方式，而是决定今天尝试一种新方法。

他的班上有 $n$ 名学生，学号分别为 $1$ 到 $n$。他知道今天恰好有 1 名学生缺席。为了确定谁缺席了，他可以向全班提出若干查询。每次查询中，他给出两个整数 $l$ 和 $r$（满足 $1\leq l\leq r\leq n$），所有学号在 $[l, r]$ 范围内的学生将举手。随后他统计举手人数，从而推断缺席学生的学号是否落在该区间内。

一切看似顺利，直到他的助教注意到了一件事——学生们不诚实！某些学号在给定区间内的学生可能不举手，而某些学号不在该区间内的学生却可能举手。但学生们不想引起太多怀疑，因此对任意一次查询 $(l,r)$，仅可能出现以下 4 种情况：

1. 真阳性（True Positive）：实际在场的学生数为 $r-l+1$，且举手人数也为 $r-l+1$；
2. 真阴性（True Negative）：实际在场的学生数为 $r-l$，且举手人数也为 $r-l$；
3. 假阳性（False Positive）：实际在场的学生数为 $r-l$，但举手人数为 $r-l+1$；
4. 假阴性（False Negative）：实际在场的学生数为 $r-l+1$，但举手人数为 $r-l$。

前两种情况称为“诚实回答”，后两种情况称为“不诚实回答”。学生们可以事先共同商定一种策略（该策略对 1048576 老师是未知的）。同时，学生们既不想引起怀疑，又想制造尽可能多的混乱，因此他们的策略始终满足以下两个条件：

1. 学生们绝不会连续三次诚实回答；
2. 学生们绝不会连续三次不诚实回答。

1048576 老师对学生的这种行为感到十分沮丧。因此，他愿意最多标记 2 名学生为缺席者（尽管他清楚实际上只有 1 人缺席）。若实际缺席的学生包含在这至多 2 名被标记的学生之中，则本次点名视为成功。此外，由于课堂时间有限，他最多只能进行 $\lceil\log_{1.116}{n}\rceil-1$ 次查询（数字虽奇怪，但确实如此）。请帮助他完成一次成功的点名。

交互流程

首先读入一行，包含一个整数 $t$（$1\leq t\leq 2048$），表示你必须解决的独立测试用例数量。

对每个测试用例，先读入一行，包含一个整数 $n$（$3\leq n\leq 10^5$）。随后你最多可进行 $\lceil\log_{1.116}{n}\rceil-1$ 次查询。

• 要提出一次查询，请输出一行，格式为 ? l r（不含引号），其中 $1\leq l\leq r\leq n$。然后读入一行，包含一个整数 $x$（满足 $r-l\leq x\leq r-l+1$），表示对应查询中举手的学生人数。

• 要标记一名学生为缺席者，请输出一行，格式为 ! a（不含引号），其中 $1\leq a\leq n$。然后读入一个整数 $y$（$y\in\{0,1\}$）。若学号为 $a$ 的学生确实缺席，则 $y = 1$；否则 $y = 0$。注意：该操作不计入查询次数，但你最多只能执行 2 次。

• 要结束当前测试用例，请输出一行，格式为 #（不含引号）。之后你必须继续处理剩余的测试用例。

如果你提出的查询次数超过限制，或提出非法查询，将得到“Wrong answer”判据。

保证所有测试用例的 $n$ 之和不超过 $10^5$。

在输出答案后，务必输出换行符并刷新输出缓冲区，否则你会收到 “Idleness limit exceeded” 判据。刷新缓冲区的方法如下：

• C++ 中使用 fflush(stdout) 或 cout.flush()；
• Java 中使用 System.out.flush()；
• Pascal 中使用 flush(output)；
• Python 中使用 stdout.flush()；
• 其他语言请查阅相应文档。

注意：本题评测器是自适应的，即回答可能根据你的查询而变化，但始终与约束条件及之前所有查询的回答保持一致。

Hack 输入格式

本题的测试用例同时支持非自适应评测器和自适应评测器。你可以使用非自适应评测器进行 hack。

输入的第一行是一个整数 $t$（$1\leq t\leq 2048$）。

每个测试用例的第一行包含三个整数 $g$、$n$ 和 $x$，其中 $g = 1$（用于标识该测试用例应使用非自适应评测器），$n$（$3 \leq n \leq 10^5$）表示班级学生总数，$x$（$1 \leq x \leq n$）表示实际缺席学生的学号。你必须确保所有测试用例的 $n$ 之和不超过 $10^5$。

每个测试用例的第二行是一个字符串 $S$（$1 \leq |S| \leq 120$，且 $S_i \in \{\texttt{T}, \texttt{F}\}$）。该字符串表示“真假序列”的模式：若 $S_{(i-1)\bmod |S|+1} = \texttt{T}$，则第 $i$ 次查询中学生将诚实回答；否则将不诚实回答。你还必须确保：不存在下标 $i$，使得

$$S_{(i-1)\bmod |S|+1} = S_{i\bmod |S|+1} = S_{(i+1)\bmod |S|+1}.$$

For the first test case, the student with roll number $2$ is absent and the truth sequence (see section for hacks) is TFFTFTTF. During execution of your solution, this test case will use a non-adaptive grader.

For the second test case, the student with roll number $4$ is absent, and the truth sequence is FFTFTTFT. During the execution of your solution, in this test case your program will interact with an adaptive grader. So, the actual answer might be different depending on your queries but will always remain consistent with the responses to the previous queries.

对于第一个测试用例，学号为 $2$ 的学生缺席，真实序列（参见“Hack”章节）为 TFFTFTTF。在您的程序运行此测试用例时，将使用非自适应评测器（non-adaptive grader）。

对于第二个测试用例，学号为 $4$ 的学生缺席，真实序列为 FFTFTTFT。在您的程序运行此测试用例时，将与一个自适应评测器（adaptive grader）进行交互。因此，实际答案可能因您的查询而异，但始终会与之前所有查询的响应保持一致。