我们定义合法括号序列为以下字符串之一： 空字符串； 字符串 $(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 = '('$ 且 $B_j = ')'$； $i = j-1$，或者子序列 $C = B_{i+1}B_{i+2} \dots 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$ 的字符串 $B$，表示与输入字符串匹配的字典序最小的合法括号序列，如果不存在，则输出 -1。

数据范围

• $2 \le N \le 100\,000$
• 对于部分测试点，$N \le 18$。
• 对于部分测试点，$N \le 2\,000$。
• 如果存在一个下标 $i$（$1 \le i \le N$），使得对于所有 $j < i$ 都有 $A_j = B_j$，且 $A_i < B_i$，则称括号序列 $A$ 的字典序小于括号序列 $B$。
• 字符 '(' 的字典序小于字符 ')'。

样例

输入格式 1

abbaaa

输出格式 1

(()())

说明

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

输入格式 2

abab

输出格式 2

-1

说明

不存在与给定字符串匹配的合法括号序列。