By a correct bracketing we mean a string consisting of brackets
( and ), in which the number of opening brackets is equal to the number of closing brackets and
each prefix of the string contains at least as many opening brackets, as closing brackets.
This way, ()() is a correct bracketing, while ())( is not, because prefix ())
contains more closing brackets than opening brackets.
For a given pair of bracketings of length , we say that the earlier bracketing is the one
which has an opening bracket in the first position, where these bracketings differ.
Such an ordering is equivalent to lexicographical ordering, assuming that .
Write a program which:
reads from the standard input numbers and ,
finds lexicographically -th bracketing of length (bracketings are numbered starting from one),
writes result to the standard output.
Input contains exactly two integers and (, ), separated by a single space.
In the first and only line your program should output a bracketing of length , which is the -th bracketing among all correct
bracketings of length . Input data is prepared in such a way that the bracketing your program is supposed to find always exists.