Bracket Strings

Time limit2sMemory limit128 MB

Summary

Given N and K, find the K-th lexicographically smallest string of length N over '(' and ')' that is not a valid bracket string, using combinatorial counting.

Level: Medium7 of 10
Topics: Combinatorics, Dynamic programming, Math, Greedy
Solved: No attempts yet

Problem

A bracket string is defined as follows.

The empty string is a bracket string.
If S is a bracket string, then (S) is also a bracket string.
If S and T are bracket strings, then ST is also a bracket string.
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.

Input

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

Output

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

Constraints

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

Examples4

Example 1
Input
```
4 0
```
Expected output
```
((((
```
Example 2
Input
```
4 4
```
Expected output
```
())(
```
Example 3
Input
```
6 63
```
Expected output
```
-1
```
Example 4
Input
```
7 13
```
Expected output
```
((())()
```