D. Beautiful Permutationtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputThis is an interactive problem.There is a permutation$$$^{\text{∗}}$$$ $$$p$$$ of length $$$n$$$.Someone secretly chose two integers $$$l, r$$$ ($$$1 \le l \le r \le n$$$) and modified the permutation in the following way: For every index $$$i$$$ such that $$$l \le i \le r$$$, set $$$p_i := p_i + 1$$$. Let $$$a$$$ denote the resulting array obtained by modifying the permutation.You are given an integer $$$n$$$ denoting the length of the permutation $$$p$$$.In one query, you are allowed to choose two integers $$$l, r$$$ ($$$1 \le l \le r \le n$$$) and ask for the sum of the subarray either of the original permutation $$$p[l \dots r]$$$ or of the modified array $$$a[l \dots r]$$$. The answer to such a query will be the corresponding integer sum.Your task is to find the pair $$$(l, r)$$$ that was chosen to obtain $$$a$$$ in no more than $$$\bf{40}$$$ queries.$$$^{\text{∗}}$$$A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in any order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation (the number $$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$, but the array contains $$$4$$$). InputThe first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.Each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2\cdot10^4$$$) — the length of the permutation.It is guaranteed that the sum of $$$n$$$ over all the test cases does not exceed $$$2\cdot10^4$$$.InteractionThe interaction for each test case begins by reading the integer $$$n$$$.You can ask two types of queries. Print "$$$ \texttt{1 l r} $$$" ($$$1 \le l \le r \le n$$$).In response, you should read a line containing a single integer $$$x$$$ — the sum of the subarray of the original permutation. (Formally, $$$x = p_l + p_{l + 1} + \dots + p_r$$$). Print "$$$ \texttt{2 l r} $$$" ($$$1 \le l \le r \le n$$$).In response, you should read a line containing a single integer $$$y$$$ — the sum of the subarray of the modified array. (Formally, $$$y = a_l + a_{l + 1} + \dots + a_r$$$). The permutation $$$p$$$ and the chosen integers $$$l$$$, $$$r$$$ are fixed beforehand and can't be changed during the time of interaction.You can output the final answer by printing "$$$ \texttt{! l r} $$$", where $$$l$$$, $$$r$$$ denote the integers that were chosen to obtain $$$a$$$. After printing the answer, your program should proceed to the next test case or terminate if there are no more.You can ask no more than $$$40$$$ queries per testcase. Printing the answer doesn't count as a query. If your program performs more than $$$40$$$ queries for one test case or makes an invalid query, you may receive a Wrong Answer verdict.After printing a query, do not forget to output the end of line and flush$$$^{\text{∗}}$$$ the output. Otherwise, you will get Idleness limit exceeded.HacksTo make a hack, use the following test format.The first line should contain a single integer $$$t$$$ $$$(1 \le t \le 10^4)$$$ — the number of testcases.The first line of each test case should contain a single integer $$$n$$$ ($$$1 \le n \le 2\cdot10^4$$$) — the length of the permutation $$$p$$$.The second line of each test case should contain $$$n$$$ integers $$$p_i$$$ ($$$1 \le p_i \le n$$$) — denoting the permutation $$$p$$$.The third line of each test case should contain two space-separated integers $$$l$$$, $$$r$$$ ($$$1 \le l \le r \le n$$$) — the chosen integers.For example, the following is the hack format of the example test: 233 1 22 242 1 3 42 4$$$^{\text{∗}}$$$To flush, use: fflush(stdout) or cout.flush() in C++; System.out.flush() in Java; flush(output) in Pascal; stdout.flush() in Python; see documentation for other languages ExampleInput2
3
4
5
4
8
8
9Output
1 1 2
2 1 2
! 2 2
1 2 4
2 1 3
2 3 4
! 2 4
NoteFor the first testcase, $$$p = [3, 1, 2]$$$ and $$$l = 2$$$, $$$r = 2$$$. Hence, the modified array $$$a$$$ will be equal to $$$[3, 2, 2]$$$.So, querying "$$$\texttt{1 1 2}$$$" gives $$$p_1 + p_2 = 3 + 1 = 4$$$. And querying "$$$\texttt{2 1 2}$$$" gives $$$a_1 + a_2 = 3 + 2 = 5$$$.For the second testcase, $$$p = [2, 1, 3, 4]$$$ and $$$l = 2$$$, $$$r = 4$$$.Note that the queries shown in the sample test are only for demonstration purposes, and they may not correspond to any optimal solution.