这是一个交互式问题。

小 Anya 是一名竞技编程选手。她也想为比赛出题！ Anya 找到比赛协调员说，她想出一个简单的题目：计算两个数的和。当然，协调员回答说这个题目已经有了。 Anya 想了一会儿，提议不仅要计算两个数的和，而是计算 10 000 个数的和。不幸的是，协调员再次回答说，类似的题目已经在练习赛中使用过了。 Anya 又想了一会儿，提议计算 100 000 000 个数的和。协调员考虑了一会儿，但随后指出测试数据对于比赛服务器来说太大了，无法处理。 于是 Anya 建议将题目改为交互式，不再存储测试数据，而是在运行时动态生成。协调员对此产生了兴趣，并询问测试数据究竟将如何生成。 就在那时，Anya 想起了 RANDU，这是最早广泛使用的伪随机数生成器之一，并提出了以下方案。让评测系统以一个整数 $s$ 开始，其范围从 $0$ 到 $2^{31}-1$，该整数在每个测试点中是预先固定但保密的。为了获得序列中的下一个数 $x$，将 $s$ 变为 $(s \cdot 65\,539) \pmod{2^{31}}$，然后将 $x = s \pmod{1\,000\,000}$ 提供给选手。选手的任务是计算我们将提供给他们的所有 $x$ 的总和。 协调员再次考虑并同意了，但要求在交互协议中增加一种可能性，即在所有数字生成之前给出答案。Anya 不禁感到疑惑：为什么需要这样做？但也同意了。

解决 Anya 问题的通用版本。在接收到按照上述方式生成的 $n$ 个伪随机数序列的同时，求出所有这些数字的总和。

交互

首先，在单独的一行中给出一个整数 $n$ ($1 \le n \le 100\,000\,000$)。之后，选手可以提出 $0$ 到 $n$ 个问题，最后给出答案。

要询问下一个问题，请在单独的一行中打印 “? $t$”，其中 $t$ 是目前为止接收到的序列元素的总和。

要给出答案，请在单独的一行中打印 “! $a$”，其中 $a$ 是序列中所有 $n$ 个元素的总和。之后，优雅地终止程序。

为了防止输出缓冲，请在打印每一行后刷新输出缓冲区：例如，在 C 或 C++ 中使用 fflush(stdout)，在 Java 中使用 System.out.flush()，在 Pascal 中使用 flush(output)，或者在 Python 中使用 sys.stdout.flush()。

样例

输入格式 1

4
5
327695
966125
847495

输出格式 1

? 0
? 5
? 327700
? 1293825
! 2141320

说明

样例中括号内的内容为评测系统内部的秘密数字 $s$ 的变化过程，选手程序无法直接获取。