Задача . F. Магниты

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

Kochiya Sanae играет с магнитами. Когда она поняла, что некоторые из этих магнитов размагничены, ей стало любопытно их найти.

Есть \(n\) магнитов, которые могут быть одного из следующих \(3\) типов:

• N
• S
• - — эти магниты размагничены.

Обратите внимание, что вы не знаете типы этих магнитов заранее.

У вас есть устройство, которое может измерять силу между магнитами, и вы можете использовать его не более \(n+\lfloor \log_2n\rfloor\) раз.

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

Тогда устройство покажет силу, которую эти магниты производят. Формально, пусть \(n_1,s_1\) — число магнитов типов N и S соответственно в левой части и \(n_2,s_2\) — в правой, тогда сила между ними будет равна \(n_1n_2+s_1s_2-n_1s_2-n_2s_1\). Обратите внимание, что cила может быть как положительной, так и отрицательной (и нулем).

Однако, если абсолютное значение силы (модуль силы) будет строго больше \(n\), машина развалится на части.

Вы должны найти все магниты типа - (все размагниченные), без поломки машины.

Заметьте, что интерактор не адаптивен. Типы магнитов фиксируются перед началом взаимодействия и не изменяются при запросах.

Гарантируется наличие не менее \(2\) магнитов, тип которых не равен -, и по крайней мере \(1\) магнита типа -.

Для каждого набора входных данных сначала следует читать целое число \(n\) (\(3 \leq n \leq 2000\)) — число магнитов.

Гарантируется, что общая сумма всех \(n\) по всем наборам входных данных не превышает \(2000\).

После этого можно вставить несколько магнитов в машину и сделать запрос из условия.

Вы должны вывести каждый запрос в три строки:

• В первой строке выведите «? l r» (без кавычек), где \(l\) и \(r\) (\(1 \leq l,r < n\), \(l+r \leq n\)) соответственно обозначают количество поставленных магнитов в левую и в правую части.
• Во второй строке выведите \(l\) целых чисел \(a_1, \dots, a_l\) (\(1 \leq a_i \leq n\), \(a_i \neq a_j\) если \(i \neq j\)) — индексы магнитов, которые вы положили влево.
• В третьей строке выведите \(r\) целых чисел \(b_1, \dots, b_r\) (\(1 \leq b_i \leq n\), \(b_i \neq b_j\) if \(i \neq j\)) — индексы магнитов, которые вы положили вправо.
• Один и тот же магнит нельзя поместить в обе стороны в одном запросе. Формально, вы должны гарантировать, что \(a_i \neq b_j\) для любых \(i\) и \(j\). Однако, вы можете оставить некоторые магниты неиспользованными.

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

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

После этого следует прочитать целое число \(F\) —, силу, которую создают эти магниты.

Обратите внимание, что если ваш запрос недействителен (лимит запросов превышен, машина ломается, либо параметры не удовлетворяют ограничениям), интерактор немедленно прекратит работу. В этом случае завершите работу программы, чтобы получить вердикт Неправильный ответ вместо произвольного вердикта.

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

• «! k A», где \(k\) — количество найденных магнитов, а \(A\) — массив, состоящий из \(k\) различных целых чисел от \(1\) до \(n\), обозначающий индексы найденных магнитов типа -. Элементы \(A\) можно вывести в произвольном порядке.
• После этого, если это был последний набор входных данных, вы должны завершить работу своей программы, в противном случае вы должны продолжить работу со следующим набором входных данных.

Заметьте, что интерактор не адаптивен. Типы магнитов фиксируются перед началом взаимодействия и не изменяются при запросах.

Взломы

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

Первая строка содержит единственное целое число \(t\) (\(1 \leq t \leq 100\)) — количество наборов входных данных во взломе.

Каждый из следующих \(t\) наборов входных данных должен быть выведен в двух строках:

• В первой строке содержится одно целое число \(n\) (\(3 \leq n \leq 2000\)) — количество магнитов.
• Во второй строке находится строка \(S\) длиной \(n\), состоящая только из N, S и -, обозначающая типы магнитов.
• В каждом из наборов входных данных должно быть по крайней мере \(2\) магнита, чей тип не равен -, и по крайней мере \(1\) магнит типа -. При этом общая сумма \(n\) во всем наборам входных данных должна не превышать \(2000\).