题目描述

你得到了一个仅包含左圆括号 ( 和右圆括号 ) 的字符串，但其中的括号并不配对。为了使这个字符串变得更好看，你希望在字符串中插⼊尽可能少的圆括号（可以在任意位置插⼊任意数量的括号，但已有的括号不能改变），使修改后的字符串括号配对。

输入格式

输⼊一行一个字符串，为括号未全部配对的圆括号序列。

输出格式

输出一行，为插⼊圆括号后配对的字符串。如有多种长度最短的方案，输出任意⼀个即可。

(())()(

(())()()

))((

(())()()

提示

对于 $60\%$ 数据，输⼊字符串长度不超过 $10$。

对于 $100\%$ 的数据，输⼊字符串长度不超过 $10^3$。

本题原始满分为 $15\text{pts}$。