题目描述

本题是交互题。

交互器预先确定了一个长度为 $n$ 的排列 $p$，并秘密选择两个整数 $L,R$，满足 $1\le L\le R\le n$。

随后，交互器将排列中下标位于 $[L,R]$ 的每个元素都增加 $1$，得到数组 $a$。也就是说：

$$a_i=\begin{cases} p_i+1,&L\le i\le R,\\ p_i,&\text{其他情况}。 \end{cases}$$

你可以询问原排列或修改后数组的任意一个连续区间的元素和。请在每组测试中使用不超过 $40$ 次询问，确定秘密区间 $[L,R]$。

长度为 $n$ 的排列由 $1$ 到 $n$ 这 $n$ 个整数各出现恰好一次构成。

输入格式

交互开始时，交互器首先输出整数 $t$，表示测试组数。

对于每组测试，交互器输出一个整数 $n$。排列 $p$ 和秘密区间 $[L,R]$ 不会直接提供给选手程序。

本地测试所使用的隐藏输入文件格式如下：

第一行一个整数 $t$。

对于每组测试：

• 第一行一个整数 $n$；
• 第二行 $n$ 个整数，表示排列 $p$；
• 第三行两个整数 $L,R$，表示秘密区间。

输出格式

你可以进行以下两种询问：

1 l r

交互器返回原排列中 $p_l+p_{l+1}+\cdots+p_r$ 的值。

2 l r

交互器返回修改后数组中 $a_l+a_{l+1}+\cdots+a_r$ 的值。

每次询问都必须满足 $1\le l\le r\le n$。每组测试最多进行 $40$ 次询问。

确定答案后，输出：

! l r

其中 $l,r$ 是你确定的秘密区间端点。最终答案不计入询问次数。

每次输出询问或答案后都必须换行并刷新输出缓冲区。

样例

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

样例说明

样例仅展示一种可能的交互过程。

第一组测试的隐藏排列可以是 $[3,1,2]$，秘密区间为 $[2,2]$。询问原排列区间 $[1,2]$ 得到 $4$，询问修改后数组的同一区间得到 $5$。

第二组测试的隐藏排列可以是 $[2,1,3,4]$，秘密区间为 $[2,4]$。

数据范围

$1\le t\le10^4$，$1\le n\le2\times10^4$，所有测试组的 $n$ 之和不超过 $2\times10^4$。

每组测试的询问次数不能超过 $40$。