一个合法的括号序列只包含左括号 '(' 和右括号 ')' 两个字符,每一个左括号 '(' 都有匹配的右括号 ')' 并且没有多余的左括号或右括号。比如 "(())()" 、 "()" 、 "(()(()))" 都是合法的括号序列, ")(" 、 "(()" 、 "(()))(" 都不是合法的括号序列。
现在蝈蝈想让你构造出两个长度都是n的合法括号序列a和b,再给你一个长度为n的字符串c,字符串c只包含字符 '0' 和 '1' 。
合法括号序列a、b和字符串c之间要满足以下条件:
1、如果c[i]= '0' ,则a[i] ≠ b[i]
2、如果c[i]= '1' ,则a[i] = b[i]
那么请你通过字符串c,构造出合法括号序列a和b,如果有多种可能,输出任意一种即可;如果无解,则输出 "NO" 。
单组数据
第一行一个整数n,表示合法括号序列及字符串的长度(1≤n≤1e5)
接下来一行长度为n的字符串c,只包含字符 '0' 和 '1'
输出两行两个长度均为n的合法括号序列a和b,如果无解,则输出一行 "NO"
6 101101 4 1100
()()() ((())) NO