A5884 | 「CEOI2016」匹配

**译自 [CEOI2016](http://www.ceoi2016.ro/) Day2 T1「[Match](http://ceoi.inf.elte.hu/probarch/16/match-statement.pdf)」**

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

- 一个空串；
- 串 (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$。