该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

半仙在小学时就学习了勾股定理。什么是勾股定理呢？任意的直角三角形，记其最长边长度为 $c$，其余两边长度为 $a,b$，则一定有 $a^2 + b^2 = c^2$。

半仙觉得这个式子不是很好看，于是将 $b^2$ 改成了 $b$……

题目描述

这是一道交互题。

一天，半仙的数学高手朋友大诗人来半仙家做客。大诗人看见了 $a^2+b=c^2$ 这个式子，联想到了最近做的奥数题。他定义伪勾股数如下：

• 对于正整数 $b$，若存在正整数 $a,c$ 满足 $a^2+b=c^2$，则称 $b$ 为关于 $a$ 和 $c$ 的伪勾股数。

大诗人回到家，创建了一个交互器。交互器将会随机生成一个整数 $x$，而用户需要通过若干次询问来猜出 $x$ 的值。每次询问形如：

• 用户给出整数 $a,c$，交互器会返回一个 0/1 变量，表示 $x$ 是否为关于 $a$ 和 $c$ 的伪勾股数。如果返回 1，则是；如果返回 0，则不是。

大诗人将交互器交给了半仙，并要求半仙在 $1200$ 次询问内猜出这个整数 $x$。当然，有时候 $x$ 无法被猜出（即不存在满足条件的 $a,c$），此时半仙应该报告无解。

但是半仙还在研究他的竞赛题，于是他将这个问题交给了你。

交互格式

没有初始输入。

每次询问，你需要向标准输出输出一个 ?，然后输出一个空格，并跟着输出两个用空格隔开的整数 $a,c$，满足 $1\le a,c\le 10^9$，然后输出一个换行并清空缓冲区。

你可以使用如下语句来清空缓冲区：

• 对于 C/C++：fflush(stdout);
• 对于 C++：std::cout << std::flush;

特别地，对于 C++ 语言，在输出换行时如果你使用 std::endl 而不是 '\n'，也可以自动刷新缓冲区。建议使用 std::endl 以避免忘记输出换行。

然后你需要从标准输入中输入一个整数，代表评测机返回的 0/1 变量。

当你确定了 $x$ 的值，请向标准输出输出一个 !，然后输出一个空格，并跟着输出一个整数表示你猜测的 $x$，接着输出换行并清空缓冲区。程序应该在此之后停止询问。

当你确定无法通过询问得出 $x$ 的值，请向标准输出输出一个 ! -1，接着输出换行并清空缓冲区。

如果你并不清楚如何进行询问，此处给出一份询问模板：

bool query(int a,int b){
	printf("? %d %d\n",a,b);
	fflush(stdout);  
	bool f; cin >> f;
	return f;
}

将这段代码复制到程序中，你可以进行如下调用：

bool f = query(a,b); //询问? a b并将交互器的结果存到 bool 类型的变量 f 中

交互样例

0

1

0

? 1 2

? 4 5

? 114 114

! 9

样例解释

初始时，$x=9$。

• 对于第一次程序询问，$1\times1+9\neq 2\times 2$，因此返回 0。
• 对于第二次程序询问，$4\times4+9=5\times 5$，因此返回 1。
• 对于第三次程序询问，$114\times114+9\neq 114\times114$，因此返回 0。
• 第四次程序报告 $x=9$，答案正确。

数据范围

本题采用捆绑测试，对于一个子任务，你必须通过其中的所有测试点才能获得该子任务的分数。

本题开启子任务依赖，对于一个子任务，只有通过了其所依赖的所有子任务，才可以进行该子任务的评测。