Enumerating Brackets
A balanced bracket sequence is a string consisting only of the characters “(” (opening brackets) and “)” (closing brackets) such that each opening bracket has a “matching” closing bracket, and vice versa. For example, “(())()” is a balanced bracket sequence, whereas “(())(()” and “())(()” are not.
Given two bracket sequences A and B of the same length, we say that A is lexicographically smaller than B (and write A < B) if:
- A and B differ in at least one position, and
- A has a “(”, and B has a “)” in the left-most position in which A and B differ
For example “
(())()” < “
()()()” because they first differ in the second position from the left, and the first string has an “
(” in that position, whereas the second string has a “
)”. For a given length
N, the “<” operator defines an ordering on all balanced bracket sequences of length
N. For example, the ordering of the sequences of length 6 is:
- ((()))
- (()())
- (())()
- ()(())
- ()()()
Given a length N and a positive integer M, your task is to find the M-th balanced bracket sequence in the ordering.
Input
You will be given an even integer N, and a positive integer M. It is guaranteed that M will be no more than the number of balanced bracket sequences of length N.
Output
Output the M-th balanced bracket sequence of length N, when ordered lexicographically.
Limits
- 2 ≤ N ≤ 2000
- 1 ≤ M ≤ 1018
- M ≤ number of balanced bracket sequences of length N
Sample Input 1
6 4
Sample Output 1
()(())