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

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

Вам даны $$$n$$$ коробок, пронумерованных от $$$1$$$ до $$$n$$$. Коробки выглядят идентично, но каждая из них имеет скрытое значение мощности $$$a_i$$$, которое равно либо $$$1$$$, либо $$$2$$$.

Ваша задача — определить значение мощности каждой коробки. Для этого вы проводите следующий эксперимент. Изначально $$$i$$$-я коробка помещается на координату $$$i$$$ на числовой оси ($$$1 \le i \le n$$$).

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

  • «swap $$$x$$$» ($$$1 \le x \le n - 1$$$): Поменяйте местами коробки, находящиеся на координатах $$$x$$$ и $$$x + 1$$$. Обратите внимание, что это изменение является постоянным и влияет на все последующие запросы.
  • «throw $$$x$$$» ($$$1 \le x \le n$$$): Бросьте мяч в коробку, находящуюся на координате $$$x$$$. Мяч перемещается на $$$p$$$ единиц вперед к координате $$$x + p$$$, если значение мощности коробки равно $$$p$$$. Если на новой координате есть коробка, мяч снова прыгает, используя мощность этой коробки. Это продолжается до тех пор, пока мяч не приземлится на координате без коробки. В ответ вы получаете общее количество прыжков, которое сделал мяч перед остановкой.

Ваша задача — определить значение мощности каждой коробки, используя не более чем $$$\left\lceil \frac{3n}{2} \right\rceil$$$ запросов в общей сложности, учитывая как запросы swap, так и throw.

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

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

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

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$1000$$$.

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

Взаимодействие для каждого набора входных данных начинается с чтения целого числа $$$n$$$.

Чтобы сделать запрос, выведите строку в одном из следующих форматов:

  • «swap $$$x$$$» (без кавычек) ($$$1 \le x \le n - 1$$$): Поменяйте местами коробки, находящиеся на координатах $$$x$$$ и $$$x + 1$$$.

  • «throw $$$x$$$» (без кавычек) ($$$1 \le x \le n$$$): Бросьте мяч в коробку, находящуюся на координате $$$x$$$. Жюри ответит целым числом — количеством прыжков, которое сделал мяч перед остановкой.

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

Как только вы определите значение мощности каждой коробки, выведите строку в следующем формате:

  • «! $$$a_1 \space a_2 \space \ldots \space a_n$$$» (без кавычек): Здесь $$$a_i$$$ — это значение мощности коробки, изначально находящейся на координате $$$i$$$ ($$$1 \le i \le n$$$). После отправки окончательного ответа переходите к следующему набору входных данных.

Обратите внимание, что отправка окончательного ответа не учитывается в ограничении в $$$\left\lceil \frac{3n}{2} \right\rceil$$$ запросов.

Если ваша программа превысит $$$\left\lceil \frac{3n}{2} \right\rceil$$$ запросов в одном наборе входных данных, ваша программа должна немедленно завершиться, чтобы получить вердикт Неправильный ответ. В противном случае она может получить любой другой вердикт.

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

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

Интерактор является неадаптивным; значения мощности коробок остаются постоянными на протяжении всего взаимодействия.

Взломы

Чтобы совершить взлом, используйте следующий формат.

Первая строка должна содержать одно целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество наборов входных данных.

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

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 2$$$) — значение мощности каждой коробки.

Сумма $$$n$$$ по всем наборам входных данных не должна превосходить $$$1000$$$.

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

2


3

3

2

2


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


throw 2

swap 3
throw 2

throw 1

! 2 1 2 1

throw 1

swap 1
throw 1

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

Ниже приведен процесс взаимодействия в примере:

РешениеЖюриОбъяснение
2Есть $$$2$$$ набора входных данных.
4В первом наборе входных данных $$$4$$$ коробки. Скрытые значения мощности $$$a = [2,1,2,1]$$$.
throw 22Бросьте мяч в коробку, находящуюся на координате $$$2$$$. Мяч перемещается по координатам $$$2 \to 3 \to 5$$$ и останавливается на координате $$$5$$$, поэтому ответ $$$2$$$.
swap 3Поменяйте местами коробки, находящиеся на координатах $$$3$$$ и $$$4$$$. Теперь коробка $$$3$$$ находится на координате $$$4$$$, а коробка $$$4$$$ находится на координате $$$3$$$.
throw 23Бросьте мяч в коробку, находящуюся на координате $$$2$$$. Мяч перемещается по координатам $$$2 \to 3 \to 4 \to 6$$$ и останавливается на координате $$$6$$$, поэтому ответ $$$3$$$. Обратите внимание, что ответ отличается из-за обмена.
throw 13Бросьте мяч в коробку, находящуюся на координате $$$1$$$. Мяч перемещается по координатам $$$1 \to 3 \to 4 \to 6$$$ и останавливается на координате $$$6$$$, поэтому ответ $$$3$$$.
! 2 1 2 1Решение приходит к выводу, что значения мощности $$$[2,1,2,1]$$$.
2Есть $$$2$$$ коробки во втором наборе входных данных. Скрытые значения мощности $$$a = [1, 2]$$$.
throw 12Бросьте мяч в коробку, находящуюся на координате $$$1$$$. Мяч перемещается по координатам $$$1 \to 2 \to 4$$$ и останавливается на координате $$$4$$$, поэтому ответ $$$2$$$.
swap 1Поменяйте местами коробки, находящиеся на координатах $$$1$$$ и $$$2$$$. Теперь коробка $$$1$$$ находится на координате $$$2$$$, а коробка $$$2$$$ находится на координате $$$1$$$.
throw 11Бросьте мяч в коробку, находящуюся на координате $$$1$$$. Мяч перемещается по координатам $$$1 \to 3$$$ и останавливается на координате $$$3$$$, поэтому ответ $$$1$$$.
! 1 2Решение приходит к выводу, что значения мощности $$$[1,2]$$$.

Пустые строки в примере входных и выходных данных даны только для лучшей читаемости; вам не нужно выводить их в вашем решении.

Обратите внимание, что в первом наборе входных данных данные запросы на самом деле недостаточны для однозначного определения значений мощности; они даны только для иллюстрации формата ввода/вывода.