F1. Трекер поп-K (простая версия)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Это простая версия задачи. Отличие между версиями заключается в том, что в этой версии $$$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.$$$
Входные данные

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$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\}$$$.

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

2 3

3

2

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


3 2 3 1

2 1 2

! 3 1 2

4 1 1

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

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

Для запроса «3 2 3 1», жюри возвращает $$$2$$$ и $$$3$$$, потому что $$$2$$$ и $$$3$$$ являются $$$k$$$ наибольшими числами в $$$[p_3, p_1]$$$, где $$$k = \min(300, m) = \min(300, 2) = 2$$$.

Для запроса «2 1 2», жюри возвращает $$$3$$$, потому что $$$3$$$ является $$$k$$$ наибольшими числами в $$$[pos_2]$$$, где $$$k = \min(60, m) = \min(60, 1) = 1$$$.

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