UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#4936. [Ceoi2016]match

Statistics 下载数据

Description

给你一个由小写字母组成的字符串s,要你构造一个字典序最小的(认为左括号的字典序比右括号小)合法的括号
序列与这个字符串匹配,字符串和括号序列匹配定义为:首先长度必须相等,其次对于一对匹配的左括号和右括号
i,j,必须有s[i]==s[j]
无解输出-1

Input

 一行一个字符串s

2<=n<=100000

Output

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

Sample Input

abbaaa

Sample Output

(()())

Hint

Source

鸣谢alone_wolf提供翻译