题目描述

Dave 喜欢只由 '(' 和 ')' 组成的字符串。尤其是，他对平衡的字符串感兴趣。可以使用以下规则构建任何平衡的字符串：

• 字符串 "()" 是平衡的。
• 两个平衡字符串的连接仍然是平衡的。
• 如果 $T$ 是一个平衡字符串，按照 '(', $T$, ')' 的顺序连接也是平衡的。例如，"()()" 和 "(()())" 是平衡字符串。")(" 和 ")()(()" 不是平衡字符串。

Dave 有一个只由 '(' 和 ')' 组成的字符串。它满足以下条件：

• 你可以通过交换相邻字符来使其平衡，需要进行 $A$ 次交换。
• 对于任意非负整数 $B~(B \\lt A)$，你不能通过 $B$ 次交换相邻字符使其平衡。
• 它是满足上述条件的所有字符串中最短的。

你的任务是计算 Dave 的字符串。如果存在多个候选字符串，则输出字典序最小的。

输入

输入包含一个整数 $A~(1 \\le A \\le 10^9)$，表示需要进行的交换次数。

输出

在一行中输出 Dave 的字符串。如果存在多个候选字符串，则输出字典序最小的。

样例输入1

1```

### 样例输出1

```plain
)(```

存在无数个只需要进行一次交换就能平衡的字符串。Dave 的字符串是其中最短的一个。

### 样例输入2

```plain
4```

### 样例输出2

```plain
)())((```

字符串 "))(()(" 可以通过 $4$ 次交换使其平衡，但输出应为 ")())((" 因为它是字典序最小的。