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

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

На числовой прямой расположено $$$n$$$ змей. $$$i$$$-я змея находится на позиции $$$a_i$$$ и имеет скорость $$$s_i$$$. Вы знаете позицию каждой змеи, и что скорость каждой змеи является целым числом от $$$0$$$ до $$$2$$$ включительно, но вы не знаете точную скорость каждой змеи. Гарантируется, что никакие две змеи не находятся на одной и той же позиции.

Чтобы определить скорость змей, вы можете дать не более $$$3$$$ инструкций. Каждая инструкция должна быть представлена в виде бинарной строки длиной $$$m$$$, содержащей буквы L и R ($$$1 \leq m \leq 4n$$$). После получения этой инструкции змеи будут двигаться в течение $$$m$$$ секунд. На $$$i$$$-й секунде, если $$$s_i=$$$L, то все змеи движутся влево в течение этой секунды. В противном случае все змеи движутся вправо в течение этой секунды. Если две змеи находятся на одной и той же позиции в любой момент времени (включая случаи, когда время не является целым числом секунд), более быстрая змея удаляется с доски. После того как все $$$m$$$ секунд истекли, вам будет сообщено количество оставшихся змей, а также местоположение всех оставшихся змей. Обратите внимание, что каждая инструкция независима от других – это означает, что все змеи восстанавливаются и возвращаются на свои исходные позиции.

Ваша задача состоит в том, чтобы найти скорость всех змей. Однако может случиться так, что для хотя бы одной змеи определить скорость невозможно. Если это так, вы должны вывести -1 вместо ответа. Вы должны выводить -1 только в том случае, если невозможно определить скорость хотя бы одной змеи, независимо от того, какие инструкции даны. Если вы сообщите -1, когда существует последовательность из не более чем $$$3$$$ инструкций, которая уникально определяет скорость каждой змеи, вы получите вердикт Неправильный ответ. Аналогично, вы получите вердикт Неправильный ответ, если не сообщили -1, когда конфигурацию невозможно определить, даже если вы правильно угадали скорости.

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

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

Первая строка каждого набора входных данных содержит целое число $$$n$$$ – количество змей ($$$2 \leq n \leq 10^5$$$).

Вторая строка содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \leq a_1 \lt a_2 \lt \ldots \lt a_n \leq 4n$$$) – начальные позиции всех змей.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

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

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

  • ? s

Вы должны гарантировать, что $$$s$$$ содержит только буквы L и R, и имеет длину от $$$1$$$ до $$$4n$$$ включительно.

Жюри вернет строку в следующем формате:

  • $$$k\:b_1\:b_2\:\ldots\:b_k\:(1 \leq k \leq n, -10^9 \leq b_1 \lt b_2 \lt \ldots \lt b_k \leq 10^9$$$)

Здесь $$$k$$$ — количество змей, которые остались после выполнения инструкции, а $$$b_1,b_2,\ldots,b_k$$$ — их конечные позиции.

Когда вы будете готовы вывести ответ, выведите строку в следующем формате:

  • Если для хотя бы одной змеи невозможно определить скорость, выведите ! -1
  • В противном случае выведите ! $$$s_1$$$ $$$s_2$$$ $$$\ldots$$$ $$$s_n$$$ ($$$0 \leq s_i \leq 2$$$). Здесь $$$s_i$$$ должно обозначать скорость $$$i$$$-й змеи в порядке ввода.

Вывод ответа не считается инструкцией.

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

Интерактор не адаптивен. Это означает, что скорость всех змей фиксирована заранее и не изменяется в процессе взаимодействия. Также гарантируется, что существует решение – то есть полученные позиции всех змей после движений согласуются с их скоростями.

После вывода каждого запроса не забудьте вывести перевод строки и сбросить буфер вывода$$$^{\text{∗}}$$$. В противном случае вы получите вердикт Решение «зависло».

На любом шаге взаимодействия, если вы считали $$$-1$$$ вместо корректных данных, ваше решение должно немедленно завершиться. Это означает, что ваше решение получит вердикт Неправильный ответ из-за некорректного запроса или любой другой ошибки. Если программа не завершится, вы можете получить любой вердикт, так как ваша программа продолжит чтение из закрытого потока.

Взломы

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

    Первая строка должна содержать целое число $$$t$$$ – количество наборов входных данных ($$$1 \leq t \leq 10^3$$$).

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

    Вторая строка каждого набора входных данных должна содержать $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \leq a_1 \lt a_2 \lt \ldots \lt a_n \leq 4n$$$) – позиции змей.

    Третья строка каждого набора входных данных должна содержать $$$n$$$ целых чисел $$$s_1,s_2,\ldots,s_n$$$ ($$$0 \leq s_i \leq 2$$$) – скорости змей.

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

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

  • fflush(stdout) или cout.flush() в C++;
  • sys.stdout.flush() в Python;
  • смотрите документацию для других языков.
Пример
Входные данные
7
2
1 2

1 1

2
1 6

2 1 4

3
2 3 4

2 2 4

3
2 3 4

3 5 6 7

5
1 3 8 14 15

5
1 2 3 4 5

4
5 6 7 8
Выходные данные



? L

! 0 1


? LRLL

! 0 1


? RRR

! -1


? RRR

! 1 1 1


! 2 1 0 0 1


! 0 2 2 2 0


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

В первом наборе входных данных скорости змей составляют $$$0$$$ и $$$1$$$. Программа начинает с инструкции L. Правая змея перемещается с $$$2$$$ на $$$1$$$, в то время как левая змея не движется. Однако, поскольку теперь обе змеи занимают позицию $$$1$$$, змея с большей скоростью (правая змея) удаляется. Поэтому остается только одна змея, и она находится на позиции $$$1$$$. В этот момент программа решает угадать скорости змей как $$$0$$$ и $$$1$$$, что является правильным, поэтому этот набор входных данных пройден. Обратите внимание, что хотя скорости $$$[0,2]$$$ также привели бы к тому, что в конечном итоге осталась бы $$$1$$$ змея на позиции $$$1$$$, мы не можем сообщить $$$-1$$$, так как можем показать, что существует последовательность инструкций, которая различает $$$[0,2]$$$ и $$$[0,1]$$$.

В третьем наборе входных данных мы заключаем, что скорость как первой, так и третьей змеи равна $$$0$$$, и можем показать, что нет способа различить скорость средней змеи между $$$1$$$ и $$$2$$$. Поэтому ответ -1 является правильным в этом случае.