A85909.「CEOI2016」匹配

译自 CEOI2016 Day2 T1「Match」

我们定义一个合法的括号序列是如下之一：

• 一个空串；
• 串 (B)，其中 B 是一个合法的括号序列；
• LR，两个合法的括号序列 L 和 R 直接拼接而成得到的串。

令 $B$ 是一个长度为 $N$ 的合法括号序列。定义 $B_i$ 是序列 $B$ 中第 $i$ 个字符。对于两个下标 $i,j$，其中 $1\le i<j\le N$，我们称 $B_i$ 和 $B_j$ 是匹配的括号，如果满足：

• $B_i=\texttt{(}$ 且 $B_j=\texttt{)}$；
• $i=j-1$，或者子序列 $C=B_{i+1}B_{i+2}\ldots B_{j-1}$ 是合法的括号序列。

令 $S$ 是一个只包含小写英文字母的字符串。我们定义 $S_i$ 是 $S$ 串中第 $i$ 个字符。我们称一个合法的括号序列 $B$ 和 $S$ 匹配，如果满足：

• $B$ 的长度和 $S$ 相等；
• 对于任意下标 $i,j$ 对，且 $i<j$。如果 $B_i$ 和 $B_j$ 是匹配的，那么 $S_i=S_j$。

对于给定长度为 $N$ 的 $S$ 串，请找到字典序最小的合法括号序列，满足和 $S$ 匹配。如果这样的括号序列不存在，输出 $-1$。

输入一行一个长度为 $N$ 且只包含小写英文字母的串 $S$。

输出长度为 $N$ 的，和 $S$ 匹配且字典序最小的合法括号序列，如果这样的括号序列不存在，输出 $-1$。

对于全部数据，$2\le N\le 10^5$。

• 对于其中 $10$ 分的测试点，$N\le 18$。
• 对于另外 $27$ 分的测试点，$N\le 2\times 10^3$。

如果存在一个下标 $i\ (1\le i\le N)$，满足对于所有 $j<i$，都有 $A_j=B_j$，且 $A_i<B_i$，我们就称括号序列 $A$ 的字典序小于括号序列 $B$。

字符 $\texttt{(}$ 的字典序小于字符 $\texttt{)}$。