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