[ABC355] E - Guess the Sum

E - Guess the Sum

Time Limit: 2 sec / Memory Limit: 1024 MB

分数: 500 分

题面

这是一个交互式问题（您的程序通过输入和输出与判定程序进行交互）。

给定一个正整数 和整数 和 ，满足 。判定程序有一个隐藏的序列 ，由介于 和 之间的整数组成。

您的目标是找到当 除以 得到的余数。然而，您不能直接知道序列 中元素的值。相反，您可以向判定程序提出以下问题：

• 选择非负整数 和 ，使得 。令 ，。询问 除以 的余数。

设 为确定任意序列 时 除以 的余数所需的最小问题数量。您需要在 个问题内找到这个余数。

限制条件

• 所有输入都是整数。

输入和输出

这是一个交互式问题（您的程序通过输入和输出与判定程序进行交互）。

首先，从标准输入读入整数 ， 和 ：

然后，重复询问问题直到确定 除以 的余数。每个问题应以以下格式打印：

这里， 和 必须满足以下限制条件：

• 和 是非负整数。

对问题的回答将以以下格式从标准输入给出：

这里， 是问题的答案，即 除以 得到的余数，其中 ，。

如果 和 不满足限制条件，或者问题数量超过 ，则 将是 -1。

如果判定程序返回 -1，则您的程序将被视为不正确。在这种情况下，立即终止程序。

一旦确定了 除以 的余数，以以下格式打印余数 并立即终止程序：

注意

• 在每次输出末尾打印一个换行符并清空标准输出。否则，判定可能会超时。
• 如果您的输出格式不正确或者程序提前退出，判定结果将是不确定的。
• 在打印答案后立即终止程序。否则，判定结果将是不确定的。

示例

这里给出一个示例，其中 ，，，。在这种情况下，，因此您最多可以提问三次。

输入	输出	描述
3 1 5		首先给出整数 ， 和 。
? 0 1	提问 。
41		，，因此答案是 除以 的余数，即 。判定程序返回这个值。
? 1 1	提问 。
85		，，因此答案是 除以 的余数，即 。判定程序返回这个值。
? 1 2	提问 。
11		，，因此答案是 除以 的余数，即 。判定程序返回这个值。
! 37	答案是 ，因此打印这个值。