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 $ 2n $, 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 $ n $ and $ k $,
- finds lexicographically $ k $-th bracketing of length 2$ n $ (bracketings are numbered starting from one),
- writes result to the standard output.
Input Format
Input contains exactly two integers $ n $ and $ k $ ($1 ≤ n ≤ 4\,000$, $1 ≤ k ≤ 10^{18}$), separated by a single space.
Output Format
In the first and only line your program should output a bracketing of length $ 2n $, which is the $ k $-th bracketing among all correct bracketings of length $ 2n $. Input data is prepared in such a way that the bracketing your program is supposed to find always exists.
Example
Input
3 2
Output
(()())