题目描述

Tom 写下了一个长度为 $n$ 的数组 $a_1, a_2, \dots, a_n$，每个数都是正整数，但 33DAI 看不到数组里的内容。

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

问完之后，33DAI 必须报出数组中最小的是哪个数，以及它第一次出现的位置。请你帮他在允许的次数内完成这件事。

交互规则

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

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

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

• 1 l r：询问 $a_l + a_{l+1} + \dots + a_r$。要求 $1 \le l < r \le n$（区间长度至少为 $2$）。交互器会回答一行，内容是这个和。
• 2 v p：报告答案。其中 $1 \le v \le 10^6$，$1 \le p \le n$。
  • 如果 $v$ 确实等于数组中的最小值，且 $p$ 是这个最小值第一次出现的位置，交互器会输出一行 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 = 4$，$q = 10$，隐藏的数组是 $a = [5, 3, 8, 3]$）。空行只是为了排版，实际输出中不要有空行。

交互器        你的程序
4 10
              1 1 2
8
              1 1 3
16
              1 2 4
14
              2 3 2
win

样例解释

• 交互器给出 $n = 4$、最多问 $10$ 次；
• 你问 1 1 2，交互器回答 8，即 $a_1 + a_2 = 8$；
• 你问 1 1 3，交互器回答 16，即 $a_1 + a_2 + a_3 = 16$；
• 你问 1 2 4，交互器回答 14，即 $a_2 + a_3 + a_4 = 14$；
• 你报告 2 3 2：数组里最小的是 $3$，它第一次出现在第 $2$ 个位置，交互器回答 win，本测试点通过。

样例 2

见 sumq1.in 与 sumq1.ans。

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

样例 3

见 sumq2.in 与 sumq2.ans。

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

数据范围

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

• $3 \le n \le 1000$；
• $1 \le a_i \le 10^6$；
• $q \ge n$。