国庆-朝日的括号序列

题目描述

Asahi 在你的电脑键盘上按了若干次 ( 和 ) ，在屏幕上打出了一段括号序列。

众所周知，按下 ( 和 ) 时，电脑会根据光标 | 的位置生成括号。光标的移动只能通过按 ( 和 ) 实现。具体规则如下：

按下 ( 时，光标 | 的左侧和右侧会各自添加一个 ( 和 ) 。举个例子，屏幕上显示 (|) 时按下 ( ，屏幕会显示 ((|)) 。

按下 ) 时，有两种情况：

1. 屏幕上光标 | 的右侧是 ) 时，光标向右移动一格。如显示(|) 时按下 ) ，屏幕会显示 ()| 。
2. 屏幕上光标 | 的右侧是 ( 或空白时，会在光标左侧添加一个 ) 。如显示()| 时按下 ) ，屏幕会显示 ())| 。

Asahi 输入括号序列后，打印下来后交给了你，然后就去河边捡石头了。注意打印后的括号序列是没有光标 | 的。你很好奇 Asahi 是怎么打出来的。请你给出一个程序，找出 Asahi 可能的最短输入序列。

输入

一行，一个仅包含 ( 和 ) 的字符串 $S$ ，表示 Asahi 给你的括号序列。$(1\le |S|\le 10^6)$

输出

一行，符合要求的最短输入序列 $T$ ；若不存在则输出 Asahi?? 。

输入样例（1）

((()))

输出样例（1）

(((

输入样例（2）

(

输出样例（2）

Asahi??

输入样例（3）

)))()

输出样例（3）

)))(

样例解释

样例（1）的输入序列也可以为 ((() 、 ((()) 、((())) 等等，都符合条件，最短的是 ((( 。

author:Layn