괄호 문자열 나열

올바른 괄호 문자열은 문자 (와 )로만 이루어진 문자열 중에서, 여는 괄호마다 짝이 되는 닫는 괄호가 있고 닫는 괄호마다 짝이 되는 여는 괄호가 있는 문자열이다. 예를 들어 (())()는 올바른 괄호 문자열이지만, (())(()와 ())(()는 아니다.

길이가 같은 두 괄호 문자열 $A$와 $B$가 다음 두 조건을 모두 만족하면 $A$가 $B$보다 사전순으로 작다고 하고 $A < B$로 쓴다.

1. $A$와 $B$가 적어도 한 자리에서 다르다.
2. $A$와 $B$가 처음으로 달라지는 가장 왼쪽 자리에서 $A$는 (이고 $B$는 )이다.

예를 들어 $(())() < ()()()$이다. 두 문자열은 왼쪽에서 두 번째 자리에서 처음 달라지는데, 앞 문자열은 그 자리가 (이고 뒤 문자열은 )이기 때문이다.

길이 $N$을 고정하면 $<$ 관계가 길이 $N$인 올바른 괄호 문자열 전체의 순서를 정한다. $N = 6$일 때 순서는 다음과 같다.

1. ((()))
2. (()())
3. (())()
4. ()(())
5. ()()()

$N$과 양의 정수 $M$이 주어질 때, 이 순서에서 $M$번째 올바른 괄호 문자열을 구하라.

첫째 줄에 짝수 $N$ ($2 \le N \le 2000$)과 양의 정수 $M$이 공백을 사이에 두고 주어진다. $M$은 $10^{18}$ 이하이고, 길이 $N$인 올바른 괄호 문자열의 개수 이하이다.

위에서 정의한 순서로 $M$번째인 길이 $N$의 올바른 괄호 문자열을 출력한다.