#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

### Enumerating Brackets

A balanced bracket sequence is a string consisting only of the characters “`(`” (opening brackets) and “`)`” (closing brackets) such that each opening bracket has a “matching” closing bracket, and vice versa. For example, “`(())()`” is a balanced bracket sequence, whereas “`(())(()`” and “`())(()`” are not.

Given two bracket sequences `A` and `B` of the same length, we say that `A` is lexicographically smaller than `B` (and write `A < B`) if:

`A`and`B`differ in at least one position, and`A`has a “`(`”, and`B`has a “`)`” in the left-most position in which`A`and`B`differ

`(())()`” < “

`()()()`” because they first differ in the second position from the left, and the first string has an “

`(`” in that position, whereas the second string has a “

`)`”. For a given length

`N`, the “<” operator defines an ordering on all balanced bracket sequences of length

`N`. For example, the ordering of the sequences of length 6 is:

`((()))``(()())``(())()``()(())``()()()`

Given a length `N` and a positive integer `M`, your task is to find the `M`-th balanced bracket sequence in the ordering.

### Input

You will be given an even integer `N`, and a positive integer `M`. It is guaranteed that `M` will be no more than the number of balanced bracket sequences of length `N`.

### Output

Output the `M`-th balanced bracket sequence of length `N`, when ordered lexicographically.

### Limits

`2 ≤ N ≤ 2000``1 ≤ M ≤ 10`^{18}`M`≤ number of balanced bracket sequences of length`N`

### Sample Input 1

6 4

### Sample Output 1

()(())

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 100 | 16 | 1s | 256MB | Minimum |

2 | 0 | 1 | 1s | 256MB | Minimum |

### Judge Compile Command

g++-8 ans.cpp -o enumeratingbrackets -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512