Скобочная последовательность — это строка из символов «(» и/или «)». Правильная скобочная последовательность — это скобочная последовательность, которую можно превратить в корректное арифметическое выражение, вставив символы «1» и «+» между исходными символами. Например:
Вам задана скобочная последовательность \(s\); обозначим ее длину за \(n\). Вы должны найти такую правильную скобочную последовательность \(t\) длины \(2n\), что \(s\) не входит в \(t\) как непрерывная подстрока, или сказать, что это невозможно.
Первая строка содержит одно целое число \(t\) (\(1 \le t \le 1000\)) — количество наборов входных данных.
Единственная строка каждого набора содержит строку \(s\) (\(2 \le |s| \le 50\)), состоящую из символов «(» и/или «)».
Для каждого набора входных данных выведите ответ на него. Если требуемой правильной скобочной последовательности не существует, выведите NO в отдельной строке. В противном случае выведите YES в первой строке, а во второй строке выведите требуемую правильную скобочную последовательность \(t\). Если ответов несколько — выведите любой из них.
4 )( (() () ))()
YES (()) YES ()()() NO YES ()(()())
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач