Unrank pairs of parentheses P20584


Statement
 

pdf   zip

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
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++