Brackets

A correct bracketing is a string of the brackets ( and ) in which the number of opening brackets equals the number of closing brackets, and every prefix contains at least as many opening brackets as closing brackets. For example, ()() is a correct bracketing, while ())( is not, because its prefix ()) has more closing brackets than opening brackets.

Given two correct bracketings of length $2n$, the earlier one is the bracketing that has an opening bracket at the first position where the two strings differ. This ordering is exactly lexicographical order when ( is treated as smaller than ).

Write a program that reads two integers $n$ and $k$, then finds and prints the lexicographically $k$-th correct bracketing of length $2n$ (bracketings are numbered starting from $1$).

A single line with two integers $n$ and $k$ ($1 \le n \le 4000$, $1 \le k \le 10^{18}$), separated by one space.

Print the correct bracketing of length $2n$ that ranks $k$-th among all correct bracketings of length $2n$ in lexicographical order. The input is guaranteed to be chosen so that this bracketing always exists.