如果一个函数的定义域是一组整数,并且它是在 $$$x$$$ 和 $$$x-1$$$、$$$f(x) = f(x-1) + 1$$$ 或 $$$f(x) = f(x-1)$$$ 中定义的,我们称该函数为好函数。
Tanya 发现了 $$$n$$$ 好的函数 $$$f_{1}、\ldots、f_{n}$$$,它们定义在从 $$$0$$$ 到 $$$10^{18}$$$ 的所有整数上,并且 $$$f_i(0) = 0$$$ 和 $$$f_i(10^{18}) = L$$$ 对于所有$$$i$$$ 从 $$$1$$$ 到 $$$n$$$。 $$$n$$$ 是 $$$L$$$ 的除数,这是一个臭名昭著的巧合。
她建议阿莱西亚玩游戏。使用一个问题 Alesya 可以向 Tanya 询问任意单个点上任意单个函数的值。要获胜,Alesya 必须选择整数 $$$l_{i}$$$ 和 $$$r_{i}$$$ ($$$0 \leq l_{i} \leq r_{i} \leq 10^{18}$$$),使得 $$$f_{i}(r_{i}) - f_{i}(l_{i}) \geq \frac{L}{n}$$$ (此处$$$f_i(x)$$$ 表示对于所有 $$$i$$$,第 $$$i$$$ 个函数在点 $$$x$$$ 处的值,使得 $$$1 \leq i \leq n$$$ 使得对于任何一对两个函数,它们的线段 $$$[l_i, r_i]$$$ 不相交(但可能有一个公共点)。
不幸的是,Tanya 不允许提出超过 $$$2 \cdot 10^{5}$$$ 的问题。帮助阿莱西亚取得胜利!
可以证明,满足上述条件的$$$[l_i, r_i]$$$总是可以选择的。
可以保证的是,Tanya 在游戏过程中不会改变功能,即交互器不具有自适应性
输入
第一行包含两个整数 $$$n$$$ 和 $$$L$$$ ($$$1 \leq n \leq 1000$$$, $$$1 \leq L \leq 10^{18}$$$, $$$n$$$ 是 $$$L$$$ 的除数) — 函数的数量及其值$$$10^{18}$$$。
互动
要询问 $$$f_i(x)$$$,请打印符号“?”不带引号,然后是两个整数 $$$i$$$ 和 $$$x$$$ ($$$1 \leq i \leq n$$$, $$$0 \leq x \leq 10^{18}$$$)。请注意,您必须刷新输出才能获得响应。
之后,您应该读取一个整数,它是点 $$$x$$$ 中第 $$$i$$$ 个函数的值。
您最多可以提出 $$$2 \cdot 10^5$$$ 问题。
要刷新,您可以使用(在打印整数和行尾之后):
- C++ 中的 fflush(stdout);
- Java 中的 System.out.flush();
- Python 中的 stdout.flush() ;
- 帕斯卡刷新(输出);
- 请参阅其他语言的文档。
黑客:
只有 $$$1 \leq L \leq 2000$$$ 的测试才允许进行黑客攻击,对于黑客攻击,请使用以下格式设置测试:
第一行应包含两个整数 $$$n$$$ 和 $$$L$$$ ($$$1 \leq n \leq 1000$$$, $$$1 \leq L \leq 2000$$$, $$$n$$$ 是 $$$L$$$ 的除数) — 函数数量及其值$$$10^{18}$$$。
$$$n$$$ 以下各行应包含 $$$L$$$ 数字 $$$l_1$$$, $$$l_2$$$, ... , $$$l_L$$$ ($$$0 \leq l_j < 10^{18}$$$ 对于所有 $$$1 \leq j \leq L$$$ 和 $$$l_j < l_{j+1}$$$ 对于所有 $$$1 < j \leq L$$$),在 $$$i$$$ 中的第 $$$l_j$$$ 意味着 $$$f_i(l_j) < f_i(l_j + 1)$$$。
输出
当您找到需要的 $$$l_i, r_i$$$ 时,打印 $$$"!"$$$(不带引号),然后在 $$$n$$$ 行中,其中的 $$$i$$$ 应包含两个整数 $$$l_i$$$、$$$r_i$$$ 除以空格。
示例
输入 #1
5 5 ? 1 0 ? 1 1 ? 2 1 ? 2 2 ? 3 2 ? 3 3 ? 4 3 ? 4 4 ? 5 4 ? 5 5 ! 0 1 1 2 2 3 3 4 4 5
输出 #1
0 1 1 2 2 3 3 4 4 4 5
注意
在示例中,Tanya 具有 $$$5$$$ 相同的函数,其中 $$$f(0) = 0$$$、$$$f(1) = 1$$$、$$$f(2) = 2$$$、$$$f(3) = 3$$$、$$$f(4) = 4$$$ 且所有剩余点的值为 $$$5$$$。
Alesya 必须为所有函数选择两个整数,以便函数在其点上的值差不小于 $$$\frac{L}{n}$$$ (这里是 $$$1$$$)并且线段交集的长度为零。
一种可能的方法是为函数 $$$1$$$ 选择对 $$$[0$$$, $$$1]$$$, $$$[1$$$, $$$2]$$$, $$$[2$$$, $$$3]$$$, $$$[3$$$, $$$4]$$$ 和 $$$[4$$$, $$$5]$$$,分别为$$$2$$$、$$$3$$$、$$$4$$$ 和$$$5$$$。