Bracket Strings

A bracket string is defined as follows.

1. The empty string is a bracket string.
2. If S is a bracket string, then (S) is also a bracket string.
3. If S and T are bracket strings, then ST is also a bracket string.
4. Every bracket string can be built using only the three rules above.

In other words, a bracket string is a string in which every opening bracket is correctly matched with a closing bracket.

This problem concerns strings that consist only of ( and ) but are not bracket strings. Call such a string a non-bracket string.

Write a program that prints the $K$-th (0-indexed) non-bracket string of length $N$ in lexicographic order. If no such string exists, print -1. In lexicographic order, ( comes before ). The lexicographically smallest string is the $0$-th string.

The first line contains two integers $N$ and $K$, separated by a space.

Print the answer string on the first line. If no string satisfies the condition, print -1.

• $1 \le N \le 50$
• $0 \le K \le 2^N - 1$