题目描述

“数字洋葱（简称为 $DO$）” 由括号组成。空括号（即没有括号）是一个 $DO$，“ $( )$ ” 也是一个 $DO$。那么，所有的 $DO$ 可以通过以下方式进行形式化的递归定义：

定义：空括号是一个 $DO$。特别地，我们称其为空 $DO$。

定义：“ $( )$ ” 是一个 $DO$。特别地，我们称其为原始 $DO$。

定义：如果 $A$ 和 $B$ 都是 $DO$，那么 “ $(A)B$ ” 这种组合形式也是一个 $DO$，其中我们称 $A$ 为该 $DO$ 的内部，$B$ 为该 $DO$ 的外部。

例如，“ $( ( ) ) ( )$ ” 是一个 $DO$，“ $( ( ( ) ) ) ( ( ) ( ) ( ) )$ ” 也是一个 $DO$，但 “ $( ) ( ) ) ( ($” 和 “ $( ( ) ) )$ ” 不是 $DO$。让我们来定义一个 $DO$ 的权重。一个 $DO$ 的权重被定义为其中 “ $($” 的数量，或者等价地，是 “ $)$ ” 的数量。因此，空 $DO$ 的权重为 $0$，原始 $DO$ “ $( )$ ” 的权重为 $1$。同样，很容易看出 “ $( ( ( ) ) ) ( ( ) ( ) ( ) )$ ” 的权重为 $7$。

此外，如果 $X = ( ( ( ) ) ) ( ( ) ( ) ( ) )$，$X$ 的内部是 $( ( ) )$，$X$ 的外部是 $( ( ) ( ) ( ) )$。当 $X = ( ( ) ( ( ) ) )$ 时，$X$ 的内部 $DO$ 是 $( ) ( ( ) )$，$X$ 的外部 $DO$ 应该是空 $DO$。

然后，我们定义所有 $DO$ 对象的价格顺序。排序规则很简单，我们可以根据它们的价格对所有 $DO$ 进行排序。这意味着给定两个不同的 $DO$，我们总能确定哪一个更贵。

[规则 1]：权重越大，价格越贵。

[规则 2]：如果两个 $DO$ 的权重相等，那么价格取决于这两个 $DO$ 的内部 $DO$。

[规则 3]：如果两个 $DO$ 的权重相同且内部 $DO$ 的价格相等，那么价格取决于这两个 $DO$ 的外部 $DO$。

让我们来解释一下这些规则。有两个 $DO$，$A$ 和 $B$。我们用 $A < B$ 表示 $B$ 比 $A$ 更贵。根据规则 1，很容易看出 $( ) < ( ( ) )$ 和 $( ( ) ) ( ) < ( ( ( ) ) ) ( )$；根据规则 2，$( ( ) ) ( ( ) ) < ( ( ( ) ) ) ( )$；根据规则 3，$( ( ) ) ( ) ( ) < ( ( ) ) ( ( ) )$。给定一个 $DO$ $X$，你的任务是写出 “下一个更贵的 $DO$（$NMED$）”，它是一个比 $X$ 更贵的 $DO$，并且不存在价格介于 $NMED$ 和 $X$ 之间的 $DO$。这意味着当我们根据价格对所有可能的 $DO$ 进行排序时，$NMED$ 是给定 $DO$ 的下一个等级的 $DO$。

输入

输入包含 $T$ 个测试用例。测试用例的数量 $T$ 在输入文件的第一行给出。每个测试用例的 $DO$ 写在单独的一行中。每行的末尾放置一个 “ $$” 符号来表示每个输入 $DO$ 表示的结束，并且 “ $($”、“ $)$ ” 和 “ $$” 之间至少有一个空格。注意，输入 $DO$ 的最小权重为 $1$，最大权重为 $30$。

输出

每个测试用例精确地输出一行。该行应包含下一个更贵的 $DO$（$NMED$），并以结束标记 “ $$” 结尾。按照输入格式的规定，“ $($”、“ $)$ ” 和 “ $$” 之间至少有一个空格。

输入样例

3
( ) $
( ) ( ) $
( ( ) ( ( ) ) ) ( ( )( ) ) $

输出样例

( ) ( ) $
( ( ) ) $
( ( ) ( ( ) ) ) ( ( ( ) ) ) $

题目来源

Taejon 2002