问题陈述
Dave 喜欢仅由 ' 组成的字符串(' 和 ')'。 他尤其对平衡弦感兴趣。 任何平衡字符串都可以使用以下规则构造:
- 一个字符串“()”是平衡的。
- 两个平衡字符串的串联是平衡的。
- 如果 $T$ 是平衡字符串,则连接 '('、$T$ 和 ')'按此顺序是平衡的。 例如,“()()“和”(()())” are balanced strings. ")(" and ")()(()" 不是平衡字符串。
Dave 有一个仅由 ' 组成的字符串(' 和 ')'。它满足以下条件:
- 您可以通过恰好交换相邻字符 $A$ 次来使其平衡。
- 对于任何非负整数 $B~(B \lt A)$,不能通过相邻字符的 $B$ 交换来使其平衡。
- 是满足上述条件的所有字符串中最短的。
你的任务是计算 Dave 的字符串。如果有多个候选者,则按字典顺序输出最小值。 与 ASCII 的情况一样,'('小于')'.
输入
输入由单个测试用例组成,其中包含整数 $A \,(1 \le A \le 10^9)$。
输出
在一行中输出 Dave 的字符串。如果有多个候选者,则按字典顺序输出最小值。
示例输入 1
1
样本输入 1 的输出
)(
有无限多个字符串只需一次交换即可平衡。戴夫的绳子是其中最短的。
示例输入 2
4
样本输入 2 的输出
)())((
字符串 "))(()(" 可以通过 $4$ 交换来平衡,但输出应该是 ")())((”因为它是字典顺序中的最小值。