Parentheses

Time limit2sMemory limit512 MB

Summary

Given A, output the shortest parentheses string whose minimum number of adjacent swaps to become balanced is exactly A, breaking ties lexicographically.

Level: Medium7 of 10
Topics: Greedy, Math, String, Combinatorics
Solved: No attempts yet

Problem

Dave likes strings that consist only of "(" and ")". He is especially interested in balanced strings. Every balanced string is built by the following rules.

The string "()" is balanced.
The concatenation of two balanced strings is balanced.
If $T$ is a balanced string, then "(", $T$ , and ")" concatenated in this order form a balanced string.

For example, "()()" and "(()())" are balanced, while ")(" and ")()(()" are not.

Dave has a string that consists only of "(" and ")" and satisfies all of the following.

It can be made balanced by swapping two adjacent characters exactly $A$ times.
For every non-negative integer $B$ with $B < A$ , it cannot be made balanced with $B$ adjacent swaps.
It is the shortest string that satisfies the two conditions above.

Find Dave's string. If several strings qualify, print the lexicographically smallest one. As in ASCII, "(" is smaller than ")".

Input

A single line contains an integer $A$ ( $1 \le A \le 10^9$ ).

Output

Print Dave's string on one line. If several strings qualify, print the lexicographically smallest one.

Hint

For $A = 1$ , infinitely many strings can be made balanced with exactly one swap, and ")(" is the shortest of them.

For $A = 4$ , the string "))(()(" can also be made balanced with 4 swaps and with no fewer, but the answer is ")())((" because it is lexicographically smaller.

Examples2

Example 1
Input
```
1
```
Expected output
```
)(
```
Example 2
Input
```
4
```
Expected output
```
)())((
```