题目描述

译自 CEOI2016 Day2 T1「Match」

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

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

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

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

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

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

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

输入格式

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

输出格式

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

样例

样例 1

输入

abbaaa

输出

(()())

另一个合法的括号序列是 (())()，但是这不是字典序最小的解。

样例 2

输入

abab

输出

-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$。

字符 ( 的字典序小于字符 )。