Скобочная последовательность называется сбалансированной, если ее можно превратить в корректное математическое выражение путем добавления символов '+' и '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\)
Если это невозможно, вы должны это определить.
Выходные данные
Если такие две сбалансированные скобочные последовательности существуют, выведите «YES» в первой строке, иначе выведите «NO». Вы можете выводить каждый символ в любом регистре.
Если ответ «YES», в двух следующих строках выведите сбалансированные скобочные последовательности \(a\) и \(b\), удовлетворяющие условиям.
Если есть несколько решений, то можно вывести любое.
Примечание
В первом наборе входных данных \(a=\)«()()()» и \(b=\)«((()))». Символы равны в позициях \(1\), \(3\), \(4\) и \(6\), ровно в тех позициях, где \(s_i=1\).
Во втором наборе входных данных \(a=\)«()()((()))» и \(b=\)«(())()()()». Символы равны в позициях \(1\), \(4\), \(5\), \(7\), \(8\), \(10\), ровно в тех позициях, где \(s_i=1\).
В третьем наборе входных данных решения нет.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
6
101101
10
1001101101
4
1100
|
YES
()()()
((()))
YES
()()((()))
(())()()()
NO
|