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

()(())
