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

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

Существует скрытая последовательность скобок $$$s$$$ длины $$$n$$$, где $$$s$$$ содержит только $$$\texttt{'('}$$$ и $$$\texttt{')'}$$$. Гарантируется, что $$$s$$$ содержит хотя бы одну $$$\texttt{'('}$$$ и одну $$$\texttt{')'}$$$.

Чтобы найти эту последовательность скобок, вы можете делать запросы. Каждый запрос имеет следующую форму: вы выбираете целое число $$$k$$$ и произвольные индексы $$$i_1, i_2, \ldots, i_k$$$ ($$$1 \le k \le 1000$$$, $$$1 \le i_1, i_2, \ldots, i_k \le n$$$). Обратите внимание, что индексы могут быть равны. Затем вы получаете целое число $$$f(s_{i_1}s_{i_2}\ldots s_{i_k})$$$, рассчитанное жюри.

Для последовательности скобок $$$t$$$, $$$f(t)$$$ — это количество непустых правильных скобочных подстрок в $$$t$$$ (подстроки должны быть непрерывными). Например, $$$f(\texttt{"()())"}) = 3$$$.

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

1. Пустая последовательность $$$\varnothing$$$ является правильной.
2. Если последовательность скобок $$$A$$$ является правильной, то $$$\mathtt{(}A\mathtt{)}$$$ также является правильной.
3. Если последовательности скобок $$$A$$$ и $$$B$$$ являются правильными, то конкатенированная последовательность $$$A B$$$ также является правильной.

Например, последовательности $$$\texttt{"(())()"}$$$, $$$\texttt{"()"}$$$ являются правильными, в то время как $$$\texttt{"(()"}$$$ и $$$\texttt{"())("}$$$ — нет.

Найдите последовательность $$$s$$$, используя не более $$$550$$$ запросов.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 1000$$$). В этот момент последовательность скобок $$$s$$$ выбрана. Интерактор в этой задаче не адаптивен. Другими словами, последовательность скобок $$$s$$$ фиксирована в каждом наборе входных данных и не меняется в процессе взаимодействия.

Чтобы сделать запрос, вам нужно выбрать целое число $$$k$$$ и произвольные индексы $$$i_1$$$, $$$i_2 \ldots i_k$$$ ($$$1 \le k \leq 1000$$$, $$$1 \leq i_1, i_2, \ldots, i_k \leq n$$$), и напечатать строку следующего вида (без кавычек):

• «$$$?\ k\ i_1\ i_2 \ldots i_k$$$»

После этого вы получаете целое число $$$f(s_{i_1}s_{i_2}\ldots s_{i_k})$$$.

Вы можете сделать не более $$$550$$$ запросов такого вида.

Далее, если ваша программа нашла последовательность скобок $$$s$$$, напечатайте строку следующего формата (без кавычек):

• «$$$!\ s_1s_2 \ldots s_n$$$»

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

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

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

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

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

Взломы

Чтобы сделать взлом, следуйте формату набора входных данных ниже.

Первая строка содержит количество наборов входных данных $$$t$$$ ($$$1 \le t \le 20$$$). Далее следует описание наборов входных данных.

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

Вторая строка каждого набора входных данных содержит последовательность скобок $$$s_1 s_2\ldots s_{n}$$$, где $$$s_i= \texttt{'('}$$$ или $$$\texttt{')'}$$$.

Последовательность скобок $$$s$$$ должна содержать хотя бы одну $$$\texttt{'('}$$$ и одну $$$\texttt{')'}$$$.