题目描述

这是一道 IO 交互题．

你有一个一次函数 $f(x)=kx+b$（$1\le x \le n-1$）．这个一次函数满足 $k,b$ 均为整数且 $k>0$．

vectorwyx 修改了这个函数，具体而言，他会选择一个整数 $t$（$1\le t \le n-1$），将这个函数在直线 $x=t$ 及右侧的部分向右平移一个单位长度，并把两部分的端点用直线段连接，得到一个分段函数 $g(x)$：

$$g(x)=\begin{cases} kx+b&1\le x<t\\ kt+b& t\le x <t+1\\ k(x-1)+b& t+1\le x \le n \end{cases} $$

请通过交互的方式得到 $t$ 的值．

交互方式

本题单个测试点中含有多组数据．

1. 首先从标准输入流读入一个整数 $T$，表示数据组数．
2. 接下来你将进行 $T$ 组数据的交互．对于每组数据，首先从标准输入流读入三个整数 $n,Q,P$．
3. 你可以通过向标准输出流输出 ? l r p $(1\le l \le r \le n$，$2\le p \le P$$)$ 的方式来询问．在单组数据中，你最多只能进行 $Q$ 次 ? 操作．交互库会根据你的询问依次做出以下判断并向标准输入流发送返回结果：
   • 若你的询问数据范围错误，回答为 $-2$．此时交互库会直接返回 WA．你需要立刻退出你的程序来避免与已经结束程序的交互库交互引起超时．
   • 若 $g(l)=g(r)$，回答为 $-1$．
   • 否则回答为 $(g(l) + g(r))\bmod p$．
4. 你可以通过向标准输出流输出 ! t 的方式来给出答案．你只能进行一次回答操作，且回答操作必须是你在每组数据中进行的最后一个操作．交互完成后，从标准输入流读入一个零或一的整数 $x$．若 $x=1$ 则代表当前数据回答正确，你需要回到步骤 $2$ 以进行下一组数据的交互．否则 $x=0$，你需要立刻退出自己的程序．

不要忘记在每次输出后刷新缓冲区，否则你将会 TLE．

下面是一些语言的刷新缓冲区操作：

• C++：fflush(stdout) 或 cout.flush()．
• C: fflush(stdout)．
• Java: System.out.flush()．
• Python: stdout.flush()．
• Pascal: flush(output)．
• 其他语言：请参考对应语言的帮助文档．

输入格式

见「交互方式」．

输出格式

见「交互方式」，

1
5 999 999

0

1

1

? 1 3 2

? 4 5 2

! 3

提示

样例解释

请注意，样例仅用来表示交互的规则，不保证有逻辑性．

样例 #1

$f(x)=3x-2$（$1\le x \le 4$）， $t=3$．

$$g(x)=\begin{cases} 3x-2&1\le x<3\\ 7& 3\le x <4\\ 3x-5& 4\le x \le 5. \end{cases} $$

所以第一次询问的结果 $(g(1) + g(3))\bmod 2 = (1+7)\bmod 2=0$，第二次询问的结果 $(g(4)+g(5))\bmod 2 = (7+ 10)\bmod 2=1$．

数据范围与约束

本题采用捆绑测试．且不存在一个 Subtask 包含其它所有 Subtask 的限制．

Subtask	分值	$n$	$Q=$	$P=$	$g(x)\le$	特殊性质
$1$	$10$	$\le 10^9$	$42$	$2\times 10^{18}$	$10^{18}$	无
$2$	$20$		$30$	$2$		斜率 $k$ 为奇数
$3$	$30$		$42$	$50$		无
$4$	$39$		$32$
$5$	$1$	$= 1162261531$			$7857125847061472735$

对于 $100\%$ 的数据，保证 $1 \le T \le 10$，$2\le n\le 1162261531$．且满足 $\forall x \in [1,n], 0 \le g(x)\le 7857125847061472735$．

提示

由于本题不存在一个 Subtask 包含其它所有 Subtask 的限制．所以数据范围中「对于 $100\%$ 的数据」部分的 $n$ 和 $g(x)$ 的上界没有任何意义．但由于直接写「对于 $100\%$ 的数据，满足 $n \ge 2$，$g(x)\ge 0$」会被某些管理以「你管这叫数据范围」打回，故此题中保留该没有意义的上界．