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

Это простая версия задачи. Отличие между версиями заключается в том, что в этой версии $$$n \le 845$$$. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

Существует скрытая перестановка $$$p$$$, которая является перестановкой $$$\{1,2,\ldots,n\}$$$. Обозначим $$$pos_i$$$ как позицию значения $$$i$$$ в $$$p$$$, т.е. $$$pos_{p_i} = i$$$.

Чтобы найти эту перестановку, вы можете задавать четыре типа запросов:

• «$$$1\ m\ i_1\ i_2\ \ldots\ i_m$$$» ($$$1 \leq m \leq n$$$, $$$i_1,\ i_2,\ \ldots,\ i_m$$$ должны быть различными). Пусть $$$k = \min(60, m)$$$. Жюри вернет $$$k$$$ наибольших чисел в $$$[p_{i_1}, p_{i_2}, \ldots, p_{i_m}]$$$ в порядке возрастания.
• «$$$2\ m\ i_1\ i_2\ \ldots\ i_m$$$» ($$$1 \leq m \leq n$$$, $$$i_1,\ i_2,\ \ldots,\ i_m$$$ должны быть различными). Пусть $$$k = \min(60, m)$$$. Жюри вернет $$$k$$$ наибольших чисел в $$$[pos_{i_1}, pos_{i_2}, \ldots, pos_{i_m}]$$$ в порядке возрастания.

• «$$$3\ m\ i_1\ i_2\ ...\ i_m$$$» ($$$1 \leq m \leq n$$$, $$$i_1,\ i_2,\ ...,\ i_m$$$ должны быть различными). Пусть $$$k = \min(300, m)$$$. Жюри вернет $$$k$$$ наибольших чисел в $$$[p_{i_1}, p_{i_2}, ..., p_{i_m}]$$$ в порядке возрастания.
• «$$$4\ m\ i_1\ i_2\ \ldots\ i_m$$$» ($$$1 \leq m \leq n$$$, $$$i_1,\ i_2,\ \ldots,\ i_m$$$ должны быть различными). Пусть $$$k = \min(300, m)$$$. Жюри вернет $$$k$$$ наибольших чисел в $$$[pos_{i_1}, pos_{i_2}, \ldots, pos_{i_m}]$$$ в порядке возрастания.

Пусть $$$c_i$$$ — количество запросов типа $$$i$$$ $$$(1 \le i \le 4)$$$. Ваше количество запросов должно удовлетворять следующим ограничениям:

• $$$c_1+c_2+c_3+c_4 \le 30.$$$
• $$$c_3+c_4 \le 1.$$$

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 845$$$). В этот момент перестановка $$$p$$$ выбрана. Интерактор в этой задаче не адаптивен. Другими словами, перестановка $$$p$$$ фиксирована в каждом наборе входных данных и не меняется в процессе взаимодействия.

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

• «$$$1\ m\ i_1\ i_2\ \ldots\ i_m$$$» ($$$1 \leq m \leq n$$$, $$$i_1, i_2, \ldots, i_m$$$ должны быть различными)

После этого вы получите $$$k=\min(60,m)$$$ целых числа — $$$k$$$ наибольших чисел в $$$[p_{i_1}, p_{i_2}, \ldots, p_{i_m}]$$$ в порядке возрастания.

Чтобы задать запрос типа $$$2$$$, вам нужно напечатать строку следующего вида (без кавычек):

• «$$$2\ m\ i_1\ i_2\ \ldots\ i_m$$$» ($$$1 \leq m \leq n$$$, $$$i_1, i_2, \ldots, i_m$$$ должны быть различными)

После этого вы получите $$$k=\min(60,m)$$$ целых числа — $$$k$$$ наибольших чисел в $$$[pos_{i_1}, pos_{i_2}, \ldots, pos_{i_m}]$$$ в порядке возрастания.

Чтобы задать запрос типа $$$3$$$, вам нужно напечатать строку следующего вида (без кавычек):

• «$$$3\ m\ i_1\ i_2\ \ldots\ i_m$$$» ($$$1 \leq m \leq n$$$, $$$i_1, i_2, \ldots, i_m$$$ должны быть различными)

После этого вы получите $$$k=\min(300,m)$$$ целых числа — $$$k$$$ наибольших чисел в $$$[p_{i_1}, p_{i_2}, \ldots, p_{i_m}]$$$ в порядке возрастания.

Чтобы задать запрос типа $$$4$$$, вам нужно напечатать строку следующего вида (без кавычек):

• «$$$4\ m\ i_1\ i_2\ \ldots\ i_m$$$» ($$$1 \leq m \leq n$$$, $$$i_1, i_2, \ldots, i_m$$$ должны быть различными)

После этого вы получите $$$k=\min(300,m)$$$ целых числа — $$$k$$$ наибольших чисел в $$$[pos_{i_1}, pos_{i_2}, \ldots, pos_{i_m}]$$$ в порядке возрастания.

Далее, если ваша программа нашла перестановку $$$p$$$, напечатайте строку следующего вида (без кавычек):

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

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

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

После вывода каждого запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для этого используйте:

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

Взломы

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

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

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

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