这是一个交互问题。
有一个 排列$$$^{\text{*}}$$$ $$$p$$$ 长度为 $$$n$$$。
有人秘密选择了两个整数 $$$l, r$$$ ($$$1 \le l \le r \le n$$$) 并按以下方式修改了排列:
- 对于每个索引 $$$i$$$ 使得 $$$l \le i \le r$$$,设置 $$$p_i := p_i + 1$$$。
让 $$$a$$$ 表示通过修改排列获得的结果数组。
给你一个整数 $$$n$$$ 表示排列 $$$p$$$ 的长度。
在一个查询中,您可以选择两个整数 $$$l, r$$$ ($$$1 \le l \le r \le n$$$) 并要求原始排列 $$$p[l \dots r]$$$ 或修改后的数组 $$$a[l \dots r]$$$ 的子数组之和。这种查询的答案将是相应的整数和。
您的任务是在不超过 $$$\bf{40}$$$ 查询中找到被选择用于获取 $$$a$$$ 的对 $$$(l, r)$$$。
$$$^{\text{*}}$$$长度$$$n$$$的排列是一个由从$$$1$$$到$$$n$$$以任意顺序的$$$n$$$不同整数组成的数组。例如,$$$[2,3,1,5,4]$$$ 是一个排列,但 $$$[1,2,2]$$$ 不是排列(数字 $$$2$$$ 在数组中出现两次),$$$[1,3,4]$$$ 也不是排列($$$n=3$$$,但数组包含 $$$4$$$)。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例包含一个整数 $$$n$$$ ($$$1 \le n \le 2\cdot10^4$$$) — 排列的长度。
保证所有测试用例的$$$n$$$总和不超过$$$2\cdot10^4$$$。
互动
每个测试用例的交互从读取整数 $$$n$$$ 开始。
您可以提出两种类型的查询。
- 打印“$$$\texttt{1 l r}$$$”($$$1 \le l \le r \le n$$$)。
作为响应,您应该读取包含单个整数 $$$x$$$ 的行 - 原始排列的子数组的总和。 (形式上,$$$x = p_l + p_{l + 1} + \dots + p_r$$$)。
- 打印“$$$\texttt{2 l r}$$$”($$$1 \le l \le r \le n$$$)。
作为响应,您应该读取包含单个整数 $$$y$$$ 的行 - 修改后的数组的子数组的总和。 (形式上,$$$y = a_l + a_{l + 1} + \dots + a_r$$$)。
排列$$$p$$$ 和选择的整数$$$l$$$、$$$r$$$ 是预先固定的,在交互过程中不能更改。
您可以通过打印“$$$\texttt{!l r}$$$”来输出最终答案,其中$$$l$$$、$$$r$$$表示选择获取$$$a$$$的整数。打印答案后,您的程序应该继续执行下一个测试用例,或者如果没有更多测试用例则终止。
每个测试用例最多可以提出 $$$40$$$ 查询。 打印答案不算作查询。 如果您的程序对一个测试用例执行超过 $$$40$$$ 查询或进行无效查询,您可能会收到 错误答案 判决。
打印查询后,不要忘记输出行尾并刷新$$$^{\text{*}}$$$ 输出。否则,你会得到 超出空闲限制.
黑客
要进行破解,请使用以下测试格式。
第一行应包含一个整数 $$$t$$$ $$$(1 \le t \le 10^4)$$$ — 测试用例的数量。
每个测试用例的第一行应包含一个整数 $$$n$$$ ($$$1 \le n \le 2\cdot10^4$$$) — 排列 $$$p$$$ 的长度。
每个测试用例的第二行应包含 $$$n$$$ 整数 $$$p_i$$$ ($$$1 \le p_i \le n$$$) — 表示排列 $$$p$$$。
每个测试用例的第三行应包含两个空格分隔的整数 $$$l$$$, $$$r$$$ ($$$1 \le l \le r \le n$$$) — 所选整数。
例如,以下是示例测试的 hack 格式:
2
3
3 1 2
2 2
4
2 1 3 4
2 4
$$$^{\text{*}}$$$要刷新,请使用:
- fflush(标准输出) or cout.flush() 在 C++ 中; Java 中的
- System.out.flush() ;
- 冲洗(输出) 帕斯卡;
- stdout.flush() 在 Python 中;
- 请参阅其他语言的文档
示例
输入复制
2 3 4 5 4 8 8 9
输出复制
1 1 2 2 1 2 ! 2 2 1 2 4 2 1 3 2 3 4 ! 2 4
注意
对于第一个测试用例,$$$p = [3, 1, 2]$$$ 和 $$$l = 2$$$,$$$r = 2$$$。因此,修改后的数组 $$$a$$$ 将等于 $$$[3, 2, 2]$$$。
因此,查询“$$$\texttt{1 1 2}$$$”给出$$$p_1 + p_2 = 3 + 1 = 4$$$。查询“$$$\texttt{2 1 2}$$$”给出$$$a_1 + a_2 = 3 + 2 = 5$$$。
对于第二个测试用例,$$$p = [2, 1, 3, 4]$$$ 和 $$$l = 2$$$,$$$r = 4$$$。
请注意,示例测试中显示的查询仅用于演示目的,它们可能不对应于任何最佳解决方案。