Глубоко в дикой местности Жили и Джили обнаружили две скобочные последовательности. Каждая из этих последовательностей имеет некую логическую структуру, но они могут и не являться правильными скобочными последовательностями. Они обнаружили, что переставляя скобки между этими двумя последовательностями, они могут исправить их. Теперь они хотят сделать обе последовательности правильными, переставляя скобки между ними.
Правильная скобочная последовательность — это последовательность, состоящая из символов «(» и «)», которую можно преобразовать в корректное математическое выражение, вставив в неё 1 и + любое количество раз. Например, последовательность «()(()())» является правильной скобочной последовательностью, тогда как «())((» или «(()» — нет.
Вам даны две последовательности скобок $$$a$$$ и $$$b$$$ четной длины $$$n$$$. Вы можете выполнять следующую операцию любое количество раз:
Определите, можно ли превратить как $$$a$$$, так и $$$b$$$, в правильные последовательности скобок.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
В первой строке каждого набора входных данных содержится одно целое число $$$n$$$ ($$$2 \leq n \leq 2\cdot 10^5$$$, $$$n$$$ — четное число) — длина строк $$$a$$$ и $$$b$$$.
Во второй строке каждого набора входных данных содержится последовательность $$$a$$$ длины $$$n$$$, состоящая из символов «(» и «)».
В третьей строке каждого набора входных данных содержится последовательность $$$b$$$ длины $$$n$$$, состоящая из символов «(» и «)».
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot 10^5$$$.
Для каждого набора входных данных выведите «YES», если возможмно преобразовать как $$$a$$$, так и $$$b$$$, в правильные скобочные последовательности, и «NO» в противном случае. Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.
72()()4))(((())4(((())))4()()(())6(((())()()))8()()()()(((())))4((((((((
YESNONOYESYESYESNO
В первом, четвёртом и шестом наборах входных данных как $$$a$$$, так и $$$b$$$ изначально представляют собой правильные скобочные последовательности.
Во втором и третьем наборе входных данных либо $$$a_1$$$, либо $$$b_1$$$ будет равно «)», поэтому невозможно сделать их правильными.
В пятом наборе входных данных итоговые скобочные последовательности могут иметь вид $$$\texttt{(((}\color{red}{\texttt{)}}\texttt{))}$$$ и $$$\texttt{()(}\color{red}{\texttt{(}}\texttt{))}$$$, где заменённые скобки выделены красным цветом.
