← 返回题目列表

AtCoder · icpc2016autumn_d

D. 括号

中文机器翻译题面 查看原题

问题陈述

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$ 交换来平衡,但输出应该是 ")())((”因为它是字典顺序中的最小值。