### Problem Statement

Well-parenthesized strings are defined using the following rules:

• The empty string is well-parenthesized.
• If S is a well-parenthesized string, then (S) is a well-parenthesized string.
• If S and T are well-parenthesized strings, then ST is a well-parenthesized string.
• Every well-parenthesized string can be created using the previous rules only.

In this problem we will deal with the complement of this set of strings: The strings that consist only of the characters '(' and ')', but are not well-parenthesized. We will call these strings mismatched.

You are given an int N and a long K. All mismatched strings of length N can be ordered lexicographically, and numbered sequentially, starting with zero. Return the string that will get the number K in this order. If there is no such string, return the empty string instead.

### Definition

 Class: MismatchedStrings Method: getString Parameters: int, long Returns: String Method signature: String getString(int N, long K) (be sure your method is public)

### Notes

-Given two different strings S and T of equal length, S is lexicographically smaller than T if it has a smaller character at the first position where they differ.
-The ASCII value of '(' is less than the ASCII value of ')'.

### Constraints

-N will be between 1 and 50, inclusive.
-K will be between 0 and 2^N - 1, inclusive.

### Examples

0)

 `4` `0`
`Returns: "(((("`
 For any length, the lexicographically smallest mismatched string consists of '(' characters only.
1)

 `4` `4`
`Returns: "())("`
 There are 14 mismatched strings of length 4. The first five are "((((", "((()", "(()(", "()((", and "())(". Note that we use a 0-based index, hence K=4 corresponds to the fifth mismatched string.
2)

 `6` `63`
`Returns: ""`
 There are less than 64 mismatched strings of length 6.
3)

 `7` `13`
`Returns: "((())()"`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10326

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13758&pm=10326

misof

#### Testers:

PabloGilberto , vorthys , ivan_metelsky

#### Problem categories:

Dynamic Programming