[CEOI2016] match

题目描述

给你一个由小写字母组成的字符串 $s$，要你构造一个字典序最小的（认为左括号的字典序比右括号小）合法的括号序列与这个字符串匹配。

字符串和括号序列匹配定义为：首先长度必须相等，其次对于一对匹配的左括号和右括号 $i,j$，必须有 $s_i=s_j$。

无解输出 -1。

输入格式

一行一个字符串 $s$。

输出格式

一行一个括号序列或者 -1。

样例 #1

样例输入 #1

abbaaa

样例输出 #1

(()())

提示

对于 $100\%$ 的数据，$2\le n\le 10^5$。