E. Интерактив — это весело
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Существует секретная последовательность $$$p_1, p_2, \cdots, p_{n}$$$, которая является перестановкой $$$\{1,2,\cdots,n\}$$$.

Обратите внимание, что $$$ \text{idx}(x) $$$ представляет индекс, где находится значение $$$x$$$.

Вы можете задавать два типа запросов в следующем формате:

  • «1 x y»

Это означает, что вы выбираете два целых числа $$$x$$$, $$$y$$$ ($$$1 \le x,y \le n$$$) и спрашиваете, выполняется ли условие $$$\text{idx}(x) \lt \text{idx}(y)$$$.

  • «2 x y z»

Это означает, что вы выбираете три целых числа $$$x$$$, $$$y$$$ и $$$z$$$ ($$$1 \leq x, y, z \leq n$$$) и спрашиваете, находится ли $$$\text{idx}(y)$$$ между $$$\text{idx}(x)$$$ и $$$\text{idx}(z)$$$. Другими словами, вам отвечают, выполняется ли условие $$$\min(\text{idx}(x), \text{idx}(z)) \leq \text{idx}(y) \leq \max(\text{idx}(x), \text{idx}(z))$$$.

Определите перестановку $$$p$$$, используя не более $$$1$$$ запроса $$$1$$$-го типа и не более $$$16n$$$ запросов типа $$$2$$$.

Входные данные

Каждый тест содержит несколько наборов входных данных. Первая строка содержит количество наборов входных данных $$$t$$$ ($$$1 \le t \le 20$$$). Далее следует описание наборов входных данных.

Протокол взаимодействия

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$3 \le n \le 100$$$). В этот момент выбирается перестановка $$$p_1, p_2, \cdots, p_{n}$$$.

Чтобы задать запрос типа $$$1$$$, вам нужно выбрать два целых числа $$$x$$$ и $$$y$$$ ($$$1 \leq x, y \leq n$$$) и вывести строку следующего вида:

  • «1 x y»

После этого вы получите:

  • «1» если выполняется условие $$$\text{idx}(x) \lt \text{idx}(y)$$$;
  • «0» в противном случае.

Чтобы задать запрос типа $$$2$$$, вам нужно выбрать три целых числа $$$x, y$$$ и $$$z$$$ ($$$1 \leq x, y, z \leq n$$$) и вывести строку следующего вида:

  • «2 x y z»

После этого вы получите:

  • «1» если выполняется условие $$$\min(\text{idx}(x), \text{idx}(z)) \leq \text{idx}(y) \leq \max(\text{idx}(x), \text{idx}(z))$$$;
  • «0» в противном случае.

Далее, если ваша программа определила перестановку, выведите строку следующего вида:

  • «! $$$p_1\ p_2\ \cdots \ p_n$$$»

Обратите внимание, что эта строка не считается запросом.

После этого переходите к следующему набору входных данных.

Если количество запросов, которые вы используете, превышает лимит, ваша программа должна немедленно завершиться, и вы получите вердикт Wrong Answer. В противном случае вы можете получить произвольный вердикт, потому что ваше решение продолжит читать из закрытого потока.

После вывода запроса или ответа для набора входных данных не забудьте вывести конец строки и сбросить вывод. В противном случае вы получите вердикт Idleness Limit Exceeded. Для этого используйте:

  • fflush(stdout) или cout.flush() в C++;
  • System.out.flush() в Java;
  • flush(output) в Pascal;
  • stdout.flush() в Python;
  • смотрите документацию для других языков.

В этой задаче интерактор не адаптивен. Другими словами, последовательность $$$p$$$ фиксирована в каждом наборе входных данных и не меняется в ходе взаимодействия.

Взломы

Чтобы взломать, следуйте формату теста ниже.

Первая строка содержит количество наборов входных данных $$$t$$$ ($$$1 \leq t \leq 20$$$). Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$3 \leq n \leq 100$$$).

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$p_1,p_2,\cdots,p_{n}$$$, которые представляют собой перестановку целых чисел от $$$1$$$ до $$$n$$$.

Пример
Входные данные
2
3

1

1

0

4

0

1

1

1
Выходные данные


2 1 1 1

2 1 3 2

1 1 2

! 2 3 1

2 2 1 4

2 1 2 3

1 4 2

! 4 3 2 1
Примечание

В первом наборе входных данных скрытая перестановка $$$p=[2,3,1]$$$. Мы можем получить $$$\text{idx}(1)=3,\text{idx}(2)=1$$$, и $$$\text{idx}(3)=2$$$.

Для запроса «2 1 1 1», жюри возвращает «1», потому что выполняется условие $$$\min(\text{idx}(1), \text{idx}(1)) \leq \text{idx}(1) \leq \max(\text{idx}(1), \text{idx}(1))$$$;

Для запроса «2 1 3 2», жюри возвращает «1», потому что выполняется условие $$$\min(\text{idx}(1), \text{idx}(2)) \leq \text{idx}(3) \leq \max(\text{idx}(1), \text{idx}(2))$$$;

Для запроса «1 1 2», жюри возвращает «0», потому что $$$\text{idx}(1) \lt \text{idx}(2)$$$ не выполняется.

Во втором наборе входных данных скрытая перестановка $$$p=[4,3,2,1]$$$.

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