D. Красивая перестановка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это интерактивная задача.

Есть перестановка$$$^{\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]$$$. Ответ на такой запрос будет соответствующей целочисленной суммой.

Ваша задача — найти пару $$$(l, r)$$$, которая была выбрана для получения $$$a$$$, не более чем за $$$\bf{40}$$$ запросов.

$$$^{\text{∗}}$$$Перестановка длины $$$n$$$ — это массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$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$$$) — выбранные целые числа.

Например, следующий тест соответствует приведенному примеру: 

2
3
3 1 2
2 2
4
2 1 3 4
2 4

$$$^{\text{∗}}$$$Чтобы сбросить, используйте:

  • fflush(stdout) или cout.flush() в C++;
  • System.out.flush() в Java;
  • flush(output) в Pascal;
  • 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$$$.

Обратите внимание, что запросы, показанные в образце теста, предназначены только для демонстрации и могут не соответствовать никакому оптимальному решению.