A. Сбалансируйте биты
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Вам дана бинарная строка $$$s$$$ длины $$$n$$$. Постройте две сбалансированные скобочные последовательности $$$a$$$ и $$$b$$$ длины $$$n$$$ такие, что для всех $$$1\le i\le n$$$ выполняется:

  • если $$$s_i=1$$$, то $$$a_i=b_i$$$
  • если $$$s_i=0$$$, то $$$a_i\ne b_i$$$

Если это невозможно, вы должны это определить.

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

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

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

Следующая строка содержит строку $$$s$$$ длины $$$n$$$, состоящую из символов 0 и 1.

Сумма $$$n$$$ во всех тестовых случаях не превышает $$$2\cdot 10^5$$$.

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

Если такие две сбалансированные скобочные последовательности существуют, выведите «YES» в первой строке, иначе выведите «NO». Вы можете выводить каждый символ в любом регистре.

Если ответ «YES», в двух следующих строках выведите сбалансированные скобочные последовательности $$$a$$$ и $$$b$$$, удовлетворяющие условиям.

Если есть несколько решений, то можно вывести любое.

Пример
Входные данные
3
6
101101
10
1001101101
4
1100
Выходные данные
YES
()()()
((()))
YES
()()((()))
(())()()()
NO
Примечание

В первом наборе входных данных $$$a=$$$«()()()» и $$$b=$$$«((()))». Символы равны в позициях $$$1$$$, $$$3$$$, $$$4$$$ и $$$6$$$, ровно в тех позициях, где $$$s_i=1$$$.

Во втором наборе входных данных $$$a=$$$«()()((()))» и $$$b=$$$«(())()()()». Символы равны в позициях $$$1$$$, $$$4$$$, $$$5$$$, $$$7$$$, $$$8$$$, $$$10$$$, ровно в тех позициях, где $$$s_i=1$$$.

В третьем наборе входных данных решения нет.