E. Сделать хорошей
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана скобочная последовательность $$$s$$$ длины $$$n$$$. Вы можете применять следующие операции произвольное количество раз (возможно, ноль) и в любом порядке:

  • Выберите индекс $$$1 \leq i \lt |s|$$$, такой, что $$$s_i = s_{i+1} = \texttt{(}$$$, и замените оба $$$s_i$$$ и $$$s_{i+1}$$$ на $$$\texttt{)}$$$.
  • Выберите индекс $$$1 \leq i \lt |s|$$$, такой, что $$$s_i = s_{i+1} = \texttt{)}$$$, и замените оба $$$s_i$$$ и $$$s_{i+1}$$$ на $$$\texttt{(}$$$.

Найдите правильную скобочную последовательность$$$^{\text{∗}}$$$ $$$t$$$, которую можно получить из $$$s$$$ с помощью описанных выше операций, или выведите $$$-1$$$, если такой $$$t$$$ не существует.

$$$^{\text{∗}}$$$Правильная скобочная последовательность — это последовательность скобок, которую можно преобразовать в корректное арифметическое выражение, вставив символы "1" и "+" между оригинальными символами последовательности. Например, последовательности скобок "()()" и "(())" являются правильными (примеры выражений: "(1)+(1)" и "((1+1)+1)"); а последовательности скобок ")(", "(" и ")" не являются правильными.

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

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

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

Вторая строка содержит одну строку $$$s$$$ — последовательность символов ( и ) длины $$$n$$$.

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

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

Для каждого набора входных данных выведите правильную скобочную последовательность $$$t$$$, которую можно получить из $$$s$$$, или выведите $$$-1$$$, если такой $$$t$$$ не существует.

Пример
Входные данные
5
4
()()
6
((())(
10
))(())())(
8
))))))))
1
(
Выходные данные
()()
-1
-1
(())(())
-1
Примечание

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

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

В четвертом наборе входных данных мы можем сделать следующее:

"))))))))" $$$\xrightarrow{i = 1}$$$ "(())))))"

"(())))))" $$$\xrightarrow{i = 5}$$$ "(())(())".