背景

团员们满脑子都是办周年庆，但小僖只想摸鱼。

于是小僖拿出了最喜欢的数列来考考你。

题目描述

小僖有一个乱序的等差数列 $A$。

你可以发出两种询问：

1. 询问原序列下标为 $x,y$ 的数在等差数列（非模意义下）中的大小关系。
2. 询问原序列下标为 $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$。

3 6
1
2
3

? 1
? 2
? 3
! 1

提示

对于 $50\%$ 的数据保证 $q=2n$。

另 $50\%$ 的数据保证 $q=2$。

对于 $100\%$ 的数据保证 $2\leq n\leq 100000$，$0\leq A_i< p$，$1\le d < p$