Enumerating Brackets

A balanced bracket sequence is a string made only of the characters ( and ) in which every opening bracket has a matching closing bracket, and every closing bracket has a matching opening bracket. For example, (())() is a balanced bracket sequence, while (())(() and ())(() are not.

Let $A$ and $B$ be two bracket sequences of the same length. We say that $A$ is lexicographically smaller than $B$, written $A < B$, when both of the following hold:

1. $A$ and $B$ differ in at least one position.
2. At the leftmost position where $A$ and $B$ differ, $A$ has a ( and $B$ has a ).

For example, $(())() < ()()()$, because the two strings first differ at the second position from the left, where the first string has a ( and the second has a ).

For a fixed length $N$, the relation $<$ orders all balanced bracket sequences of length $N$. For $N = 6$ the order is:

1. ((()))
2. (()())
3. (())()
4. ()(())
5. ()()()

Given $N$ and a positive integer $M$, find the $M$-th balanced bracket sequence of length $N$ in this order.

The first line contains an even integer $N$ ($2 \le N \le 2000$) and a positive integer $M$, separated by a space. $M$ is at most $10^{18}$, and $M$ is also at most the number of balanced bracket sequences of length $N$.

Print the $M$-th balanced bracket sequence of length $N$ in the order described above.