P7849 「JZOI-2」猜数列
题目背景
团员们满脑子都是办周年庆，但小僖只想摸鱼。
于是小僖拿出了最喜欢的数列来考考你。
题目描述
小僖有一个乱序的等差数列 $A$。
你可以发出两种询问：
1. 询问原序列下标为 $x,y$ 的数在等差数列（非模意义下）中的大小关系。
1. 询问原序列下标为 $x$ 的数在等差数列（模意义下）中的值。
但由于交互库出了点问题，你的询问 $2$ 最多能询问 $q$ 次。
给定等差数列的长度 $n$ 和询问次数 $q$，和固定的模数 $p=10^{9}+7$，求这个等差数列的公差 $d$。
**总询问次数不得超过 $2n$ 次。交互完成后请立刻输出答案。**
**交互方式：**
输入数列的长度 $n$ 和询问次数 $q$ 以开始交互。
交互过程中，您可以进行题目描述中的两种询问。
对于第一种询问，交互库将会返回 $1$ 代表 $>$ 或 $0$ 代表 $ x y`。
对于第二种询问，交互库将会返回一个正整数 $A_i$。询问格式为 `? x`。
在您确定答案后，请以 `! d` 的形式输出一行，停止交互。
在您输出一行后，请清空缓冲区：
在 C++ 中，使用 `fflush(stdout)` 或 `cout.flush()`。
在 Pascal 中，使用 `flush(output)`。
在 Python 中，使用 `stdout.flush()`。
其它语言请自行查阅文档。
**请遵循题目完成交互，发出不合法询问可能会出现 TLE，WA 等问题。**
输入格式
见交互方式。
输出格式
见交互方式。
数据保证不会有多种可能的 $d$。
说明/提示
对于 $50\%$ 的数据保证 $q=2n$。
另 $50\%$ 的数据保证 $q=2$。
对于 $100\%$ 的数据保证 $2\leq n\leq 100000$，$0\leq A_i< p$，$1\le d < p$