Unrank pairs of parentheses P20584

In general, there are many ways to place $n$ pairs of parentheses correctly. For instance, these are just a few of the 42 ways for $n = 5$:

The following rules inductively define all the correct strings made up with parentheses:

• The empty string is correct.

• All correct non-empty strings are of the kind $\mbox{\texttt{(}}x \mbox{\texttt{)}}y$, where $x$ and $y$ are correct strings.

Let $\vert s \vert$ denote the length of a string $s$. We can define as follows a total order among the correct strings with parentheses:

• The empty string is smaller than any non-empty string.

• Given two non-empty strings $s_1 = \mbox{\texttt{(}}x_1 \mbox{\texttt{)}}y_1$ and $s_2 = \mbox{\texttt{(}}x_2 \mbox{\texttt{)}}y_2$,  $s_1$ is smaller than $s_2$ if and only if:

  • $\vert s_1 \vert < \vert s_2 \vert$,

  • or $\vert s_1 \vert = \vert s_2 \vert$ and $x_1$ is smaller than $x_2$,

  • or $\vert s_1 \vert = \vert s_2 \vert$,  $x_1 = x_2$ and $y_1$ is smaller than $y_2$.

Can you write a program to compute the $i$-th correct string with $n$ pairs of parentheses?

Input

Input consists of several cases, each one with two numbers $i$ and $n$. Assume $0 \le n \le 30$ and that $i$ is between 1 and the number of correct strings with $n$ pairs of parentheses.

Output

For every case, print the $i$-th correct string with $n$ pairs of parentheses.