猜测总和

题目描述

这是一个交互式任务（你的程序通过输入输出与评测程序交互）。

给定正整数 $N$ 和满足 $0 \le L \le R \lt 2^N$ 的整数 $L$、$R$。评测程序持有隐藏的序列 $A = (A_0, A_1, \dots, A_{2^N-1})$，每个元素是 $0$ 到 $99$ 之间的整数。

你的目标是求出 $A_L + A_{L+1} + \dots + A_R$ 除以 $100$ 的余数。但是，你无法直接知道序列 $A$ 中元素的值。作为代替，你可以向评测程序提出如下问题：

选择满足 $2^i(j+1) \le 2^N$ 的非负整数 $i$ 和 $j$。设 $l = 2^i j$，$r = 2^i (j+1) - 1$，询问 $A_l + A_{l+1} + \dots + A_r$ 除以 $100$ 的余数。

设 $m$ 是无论序列 $A$ 为何值，确定 $A_L + A_{L+1} + \dots + A_R$ 除以 $100$ 的余数所需的最少询问次数。你需要在 $m$ 次询问以内求出该余数。

输入格式

这是一个交互式任务（你的程序通过输入输出与评测程序交互）。

首先，从标准输入读取整数 $N$、$L$、$R$：

$N$ $L$ $R$

接下来，每次提问后，评测程序会从标准输入给出回答：

$T$

这里，$T$ 是提问的回答；如果提问中的 $i$ 和 $j$ 不满足约束，或提问次数超过 $m$，则 $T$ 为 -1。

输出格式

重复提问，直到能确定 $A_L + A_{L+1} + \dots + A_R$ 除以 $100$ 的余数。

提问按以下格式输出到标准输出：

$?$ $i$ $j$

这里，$i$ 和 $j$ 必须满足以下约束：

• $i$、$j$ 是非负整数。
• $2^i(j+1) \le 2^N$

此时回答中的 $l = 2^i j$，$r = 2^i (j+1) - 1$。

当评测程序返回 -1 时，该提交已被视为不正确。此时请立即终止程序。

当你确定了 $A_L + A_{L+1} + \dots + A_R$ 除以 $100$ 的余数时，设该余数为 $S$，按以下格式输出，然后立即终止程序：

$!$ $S$

样例

本题为交互式任务，没有样例。

数据范围

• $1 \le N \le 18$
• $0 \le L \le R \le 2^N - 1$
• 所有输入值均为整数

提示

每次输出后都要换行并刷新标准输出（flush）。否则可能会超时（TLE）。