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 leftmost position in which $A$ and $B$ differ
For example “(())()” < “()()()” 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$ ($2 \leq N \leq 2\, 000$), and a positive integer $M$. It is guaranteed that $M$ will be no more than $10^{18}$ and no more than the number of balanced bracket sequences of length $N$ (whichever is smaller).
Output
Output the $M$th balanced bracket sequence of length $N$, when ordered lexicographically.
Sample Input 1  Sample Output 1 

6 4 
()(()) 