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

У Карла есть $$$n$$$ цветных монет, и он хотел бы отсортировать их в стопки. Монеты пронумерованы $$$1,2,\ldots,n$$$, и каждая монета либо красного, либо зеленого, либо синего цвета. Он хотел бы отсортировать монеты на три разные стопки, чтобы одна стопка содержала все красные монеты, одна стопка содержала все зеленые монеты, а одна стопка содержала все синие монеты.

К сожалению, Карл дальтоник, поэтому эта задача для него невыполнима. К счастью, у него есть друг, который может взять пару монет и сказать Карлу, имеют ли они один цвет или нет. Используя своего друга, Карл теперь считает, что он может отсортировать монеты. Порядок куч не имеет значения. Имеет значение только то, чтобы все монеты одного цвета находились в одной стопке и чтобы не было двух монет разного цвета в одной стопке.

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

Карл может задать только $$$7$$$ групп вопросов. Помогите ему найти стопки монет после сортировки.

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

Во входных данных находятся несколько (не меньше одного) тестовых случаев. В первой строке находится одно целое число $$$t$$$ $$$(1 \leq t \leq 5$$$) — количество тестовых случаев.

Первая строка описания тестового случая содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — количество монет. Если вы считали $$$-1$$$, значит вы вывели неправильный ответ в предыдущем тестовом случае и вы должны немедленно завершить работу вашей программы, иначе вы можете получить другой вердикт.

Чтобы задать запрос, выведите «Q $$$k\ x_1\ y_1\ \ldots\ x_k\ y_k$$$» ($$$1 \leq k \leq n/2, 1 \leq x_i,y_i \leq n, x_i \neq y_i$$$), где $$$k$$$ — количество пар в группе, а $$$x_i, y_i$$$ — $$$i$$$-я пара монет в группе. Каждая монета может использоваться только раз в каждой группе. Все $$$x_i$$$ и $$$y_i$$$ должны быть различны.

Считайте строку длины $$$k$$$, где $$$i$$$-й символ равен «1», если $$$x_i$$$ и $$$y_i$$$ имеют один цвет, или «0» в другом случае. Если же вы считали $$$-1$$$, то это значит, что вы сделали неправильный запрос и вам нужно завершить работу вашей программы, чтобы не получить другие вердикты.

Когда вы готовы отвечать, выведите четыре строки.

Первая строка должна содержать «A $$$k_1\ k_2\ k_3$$$» ($$$0 \leq k_1,k_2,k_3$$$ и $$$k_1+k_2+k_3 = n$$$). Числа обозначают размеры стопок.

Следующая строка должна содержать $$$k_1$$$ чисел — номера монет в первой стопке.

Следующая строка должна содержать $$$k_2$$$ чисел — номера монет во второй стопке.

Следующая строка должна содержать $$$k_3$$$ чисел — номера монет в третьей стопке.

Каждая монета должна находиться в ровно одной стопке.

Вы можете задать не более $$$7$$$ запросов в каждом тестовом случае.

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

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

Формат для взломов

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

Первая строка должна содержать одно целое число $$$t$$$ ($$$t=1$$$).

Вторая строка содержит строку $$$s$$$, которая состоит только из символов «R», «G», «B» ($$$1 \leq |s| \leq 10^5$$$). $$$i$$$-й символ строки представляет цвет $$$i$$$-й монеты.

Пример
Входные данные
3
3
1
1
1
3
1
0
0
6
000
010
100
001
000
Выходные данные
Q 1 1 2
Q 1 2 3
Q 1 1 3
A 3 0 0
1 2 3


Q 1 1 3
Q 1 2 3
Q 1 1 2
A 2 0 1
1 3

2
Q 3 1 2 3 4 5 6
Q 3 1 3 2 5 4 6
Q 3 1 4 2 6 3 5
Q 3 1 5 2 4 3 6
Q 3 1 6 2 3 4 5
A 2 2 2
1 4
2 5
3 6
Примечание

В примере есть три тестовых случая.

В первом тестовом случае есть три монеты. Мы спрашиваем о парах $$$(1,2)$$$, $$$(2,3)$$$ и $$$(1,3)$$$ в разных группах и получаем, что они все одного цвета. Таким образом, мы знаем, что все монеты одного цвета, поэтому мы можем положить их все в одну стопку. Обратите внимание, что некоторые стопки могут быть пустыми, и они должны быть обозначены пустой строкой.

Во втором тестовом случае снова три монеты. На этот раз мы только получаем, что $$$(1,3)$$$ одинаковы, а $$$(1,2)$$$ и $$$(2,3)$$$ различны. Итак, один из возможных сценариев — монеты $$$1$$$ и $$$3$$$ красного цвета, а монета $$$2$$$ зеленого цвета.

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