# Unrank pairs of parentheses P20584

Statement html

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 ( x ) y, where x and y are correct strings.

Let | s | 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 s1 = ( x1 ) y1 and s2 = ( x2 ) y2,  s1 is smaller than s2 if and only if:
• | s1 | < | s2 |,
• or | s1 | = | s2 | and x1 is smaller than x2,
• or | s1 | = | s2 |,  x1 = x2 and y1 is smaller than y2.

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 ≤ n ≤ 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.

Public test cases
• Input

```1 3
2 3
3 3
4 3
5 3
70 6
1 0
1 30
2000000000000000 30
3814986502092304 30
```

Output

```()()()
()(())
(())()
(()())
((()))
(()(()))(())

()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()
(((())()(())(()))(()())((()()(()))()))(((())(((()(()))))()))
(((((((((((((((((((((((((((((())))))))))))))))))))))))))))))
```
• Information
Author