题目描述

阿瓦的电脑上有一个长度为 $n$ 的序列，你可以进行至多 $3n+1$ 次询问，询问格式如下：

• ? 1 x y，如果你使用这个询问，则交互库会告诉你 $a_x \ \& \ 2a_y$ 的值。

• ? 2 x y，如果你使用这个询问，则交互库会告诉你 $a_x \ | \ 2a_y$ 的值。

• ? 3 x y，如果你使用这个询问，则交互库会告诉你 $a_x \oplus 2a_y$ 的值。

其中，$\&$ 表示按位与运算，$|$ 表示按位或运算，$\oplus$ 表示异或运算。

在询问后，你需要求出 $\sum_{i=1}^{n}\sum_{j=i}^{n}{(a_i \ | \ a_{i+1} \ | \ a_{i+2} \ | \ \dots \ | \ a_j)}$ 的值，由于这个数可能很大，因此你需要将结果对 $10^9 + 9$ 取模。

输入格式

本题为交互题，交互格式如下：

首先题目会给你一个正整数 $n$，然后你需要在至多 $3n + 1$ 次询问中找到答案，询问格式如下：

• ? 1 x y，如果你使用这个询问，则交互库会告诉你 $a_x \ \& \ 2a_y$ 的值。

• ? 2 x y，如果你使用这个询问，则交互库会告诉你 $a_x \ | \ 2a_y$ 的值。

• ? 3 x y，如果你使用这个询问，则交互库会告诉你 $a_x \oplus 2a_y$ 的值。

其中，$\&$ 表示按位与运算，$|$ 表示按位或运算，$\oplus$ 表示异或运算。

• ! x，在询问次数到 $3n + 1$ 次之前，你可以使用这个操作，这说明你已经知道了答案，你需要返回一个数 $x$ 表示你的答案，若你的答案 $x$ 正确，则交互库会给出 Accepted 的结果，否则，交互库会给出 Wrong Answer 的结果。

特别的，你每次询问时的 $x,y$ 都要满足 $1 \le x,y \le n$ 的条件。

每次你输出之后，请刷新缓冲区。

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

• 对于 C/C++：fflush(stdout)；
• 对于 C++：std::cout << std::flush；
• 对于 Java：System.out.flush()；
• 对于 Python：stdout.flush()；
• 对于 Pascal：flush(output)；
• 对于其他语言，请自行查阅对应语言的帮助文档。

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

输出格式

见输入格式。

样例 #1

样例输入 #1

1

3

样例输出 #1

? 3 1 1

! 1

提示

【样例解释】

只有 $1$ 满足 $1 \oplus (1 \times 2) = 3$ 的条件。

【评分方式】

若你的询问次数小于等于 $3n + 1$ 次且答案正确，可以获得 测试点 $40\%$ 的分数。

若你的询问次数小于等于 $2n + 1$ 次且答案正确，可以获得 测试点 $70\%$ 的分数。

若你的询问次数小于等于 $n + 1$ 次且答案正确，可以获得 测试点 $100\%$ 的分数。

否则，你不会获得分数。

【数据范围】

对于 $70\%$ 的数据，$n = 1$，

对于 $80\%$ 的数据，$n \le 800$，

对于 $90\%$ 的数据，$n \le 8000$，

对于 $100\%$ 的数据，$n \le 10^5$，$1 \le a_i < 2^{60}$。