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

Дана бинарная строка $$$s$$$ длины $$$2n$$$, каждый элемент которой равняется $$$\mathtt{0}$$$ или $$$\mathtt{1}$$$. Вы можете выполнять следующую операцию:

  1. Выбрать правильную скобочную последовательность$$$^\dagger$$$ $$$b$$$ длины $$$2n$$$.
  2. Пройти по всем индексам $$$i$$$ от $$$1$$$ до $$$2n$$$ по порядку. Если $$$b_i$$$ — открывающая скобка, то обозначим за $$$p_i$$$ минимальный индекс такой, что $$$b[i,p_i]$$$ — правильная скобочная последовательность. Тогда к подотрезку с $$$i$$$ по $$$p_i$$$ из бинарной строки $$$s$$$ применяется операция инвертирования$$$^\ddagger$$$. Заметим, что поскольку правильная скобочная последовательность длины $$$2n$$$ будет иметь $$$n$$$ открывающих скобок, то мы выполним $$$n$$$ операций инвертирования подотрезка над $$$s$$$.

Ваша задача — найти последовательность из не более чем $$$10$$$ операций, изменяющую все элементы $$$s$$$ на $$$\mathtt{0}$$$, или определить, что это невозможно. Заметим, что минимизировать количество операций не обязательно.

При заданных ограничениях можно доказать, что если существует способ изменить все элементы $$$s$$$ на $$$\mathtt{0}$$$, то существует способ, требующий не более $$$10$$$ операций.

$$$^\dagger$$$ Скобочная последовательность называется правильной, если ее можно превратить в корректное математическое выражение, добавив символы $$$+$$$ и $$$1$$$. Например, последовательности «(()()», «()» и «(()(())» являются правильными, а «)(», «(()» и «(())(» — не являются.

$$$^\ddagger$$$ Если мы выполним операцию инвертирования для подотрезка с $$$l$$$ по $$$r$$$ бинарной строки $$$s$$$, то мы инвертируем все значения $$$s_i$$$ такие, что $$$l \leq i \leq r$$$. Если $$$s_i$$$ инвертируется, то мы присваиваем $$$s_i := \mathtt{0}$$$, если изначально было $$$s_i = \mathtt{1}$$$, и наоборот. Например, если $$$s=\mathtt{1000101}$$$ и мы выполняем операцию инвертирования подотрезка с $$$3$$$ по $$$5$$$, то $$$s$$$ изменится на $$$s=\mathtt{1011001}$$$.

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

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

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

Вторая строка каждого набора входных данных содержит бинарную строку $$$s$$$ длины $$$2n$$$ ($$$s_i = \mathtt{0}$$$ или $$$s_i = \mathtt{1}$$$).

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

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

Для каждого набора входных данных выведите в единственной строке $$$-1$$$, если невозможно изменить все элементы $$$s$$$ на $$$\mathtt{0}$$$.

В противном случае выведите одно целое число $$$k$$$ ($$$0 \le k \le 10$$$), равняющееся количеству операций, необходимому для изменения всех элементов $$$s$$$ на $$$\mathtt{0}$$$. Затем в следующих $$$k$$$ строках выведите правильные скобочные последовательности длины $$$2n$$$, представляющие собой операции, необходимые для изменения всех элементов $$$s$$$ на $$$0$$$.

Если существует несколько способов изменить все элементы $$$s$$$ на $$$\mathtt{0}$$$, требующих не более $$$10$$$ операций, то можно вывести любой из них.

Пример
Входные данные
4
1
01
2
0000
3
100111
4
01011100
Выходные данные
-1
2
()()
()()
1
(())()
2
(((())))
()()(())
Примечание

В первом наборе входных данных можно показать, что невозможно изменить все элементы $$$s$$$ на $$$\mathtt{0}$$$.

Во втором наборе входных данных первая операция с использованием последовательности скобок $$$b = \mathtt{()()}$$$ преобразует двоичную строку $$$s=\mathtt{0000}$$$ в $$$s=\mathtt{1111}$$$. Затем вторая операция с использованием той же последовательности скобок $$$b = \mathtt{()()}$$$ преобразует двоичную строку $$$s=\mathtt{1111}$$$ обратно в $$$s=\mathtt{0000}$$$. Заметим, что поскольку все элементы $$$s$$$ изначально уже равнялись $$$\mathtt{0}$$$, то использование $$$0$$$ операций также является правильным ответом.

В третьем наборе входных данных одна операция с использованием последовательности скобок $$$b = \mathtt{(())()}$$$ изменит все элементы $$$s$$$ на $$$\mathtt{0}$$$. Операция будет происходить следующим образом:

  1. $$$b_1$$$ — открывающая скобка, а $$$p_1 = 4$$$, так как $$$b[1,4]=\mathtt{(())}$$$ — правильная скобочная последовательность. Следовательно, выполнив операцию инвертирования подотрезка с $$$1$$$ по $$$4$$$ на бинарной строке $$$s = \mathtt{100111}$$$, мы получим $$$s = \mathtt{011011}$$$.
  2. $$$b_2$$$ является открывающей скобкой, а $$$p_2 = 3$$$, так как $$$b[2,3]=\mathtt{()}$$$ является правильной скобочной последовательностью. Следовательно, выполнив операцию инвертирования подотрезка с $$$2$$$ по $$$3$$$ на бинарной строке $$$s = \mathtt{011011}$$$, мы получим $$$s = \mathtt{000011}$$$.
  3. $$$b_3$$$ не является открывающей скобкой, поэтому на этом шаге операция инвертирования не выполняется.
  4. $$$b_4$$$ не является открывающей скобкой, поэтому на этом шаге операция инвертирования не выполняется.
  5. $$$b_5$$$ является открывающей скобкой, а $$$p_5 = 6$$$, так как $$$b[5,6]=\mathtt{()}$$$ является правильной скобочной последовательностью. Следовательно, выполнив операцию инвертирования подотрезка с $$$5$$$ по $$$6$$$ для бинарной строки $$$s = \mathtt{000011}$$$, мы получим $$$s = \mathtt{000000}$$$.
  6. $$$b_6$$$ не является открывающей скобкой, поэтому на этом шаге операция инвертирования не выполняется.

В четвертом наборе входных данных первая операция с использованием скобочной последовательности $$$b = \mathtt{(((())))}$$$ преобразует бинарную строку $$$s = \mathtt{01011100}$$$ в $$$s = \mathtt{11111001}$$$. Затем, вторая операция с использованием скобочной последовательности $$$b = \mathtt{()()(())}$$$ преобразует бинарную строку $$$s = \mathtt{11111001}$$$ в $$$s=\mathtt{00000000}$$$.