题目描述

Tom 写了一个长度为 $n$ 的数组 $a_1, a_2, \dots, a_n$，每个数都是 $0$ 到 $2^{30}-1$ 之间的整数，33DAI 看不到数组里的内容。

33DAI 可以问 Tom：任选两个下标 $l < r$，Tom 会告诉他 $a_l \oplus a_{l+1} \oplus \dots \oplus a_r$ 的值。注意每次询问的区间至少要包含 $2$ 个数，也就是不允许直接问某一个位置上的数。

问完之后，33DAI 必须报出：在所有满足 $1 \le i < j \le n$ 的数对中，$a_i \oplus a_j$ 的最大值。

本题用到的运算：

• 按位异或 $\oplus$：把两个数写成二进制后逐位比较，相同得 $0$、不同得 $1$。例如 $6 \oplus 3 = 5$（$110_2 \oplus 011_2 = 101_2$）。C++ 中写 a ^ b。

交互规则

本题没有输入文件，你通过与交互器对话来获取信息。你的程序需要从标准输入读入数据、向标准输出写数据。

第一步：从标准输入读入一行两个整数 $n, q$（$3 \le n \le 1000$，$1 \le q \le 10^6$），其中 $n$ 是数组长度，$q$ 是你最多可以询问的次数。

接下来的每一次操作，你向标准输出写一行，格式必须是下面两种之一：

• 1 l r：询问 $a_l \oplus a_{l+1} \oplus \dots \oplus a_r$。要求 $1 \le l < r \le n$（区间长度至少为 $2$）。交互器会回答一行，内容是这个异或值。
• 2 v：报告答案。其中 $0 \le v < 2^{30}$，表示你认为的最大异或值。
  • 如果 $v$ 确实等于 $\max_{1 \le i < j \le n} (a_i \oplus a_j)$，交互器会输出一行 win，本题该测试点通过；
  • 否则本题该测试点判为 Wrong Answer。

报告答案的那一次操作不计入询问次数。

每次输出一行后，必须立即刷新输出缓冲区，否则交互器会读到旧数据而判错。C++ 中的做法是：

printf("1 %d %d\n", l, r);
fflush(stdout);
// 用 cout 的话写 cout << "1 " << l << " " << r << endl;（endl 会刷新）或 cout.flush();

限制：询问次数不能超过 $q$ 次，否则判为 Wrong Answer。

样例 1

下面是一次合法的交互过程（$n = 3$，$q = 100$，隐藏的数组是 $a = [6, 3, 5]$）。空行只是为了排版，实际输出中不要有空行。

交互器        你的程序
3 100
              1 1 2
5
              1 2 3
6
              1 1 3
0
              2 6
win

样例解释

• 交互器给出 $n = 3$、最多问 $100$ 次；
• 你问 1 1 2，交互器回答 5，即 $a_1 \oplus a_2 = 6 \oplus 3 = 5$；
• 你问 1 2 3，交互器回答 6，即 $a_2 \oplus a_3 = 3 \oplus 5 = 6$；
• 你问 1 1 3，交互器回答 0，即 $a_1 \oplus a_2 \oplus a_3 = 6 \oplus 3 \oplus 5 = 0$；
• 你报告 2 6：三对数的异或值分别是 $6 \oplus 3 = 5$、$6 \oplus 5 = 3$、$3 \oplus 5 = 6$，最大值是 $6$，与你的答案相同，交互器回答 win，本测试点通过。

样例 2

见 xorq1.in 与 xorq1.ans。

其中 .in 就是本次交互开始时交互器给出的 $n$ 与 $q$；.ans 是本测试点隐藏的数组 $a$，供你本地调试时查看，实际评测时你并看不到它。

样例 3

见 xorq2.in 与 xorq2.ans。

其中 .in 就是本次交互开始时交互器给出的 $n$ 与 $q$；.ans 是本测试点隐藏的数组 $a$，供你本地调试时查看，实际评测时你并看不到它。

数据范围

对于所有测试数据，保证：

• $3 \le n \le 1000$；
• $0 \le a_i < 2^{30}$；
• $q \ge n$。