I spent one day solving [this problem](https://code.google.com/codejam/contest/4214486/dashboard#s=p3) and couldn't find a solution to pass the large dataset.

Problem

An n parentheses sequence consists of n "("s and n ")"s.

Now, we have all valid n parentheses sequences. Find the k-th smallest sequence in **lexicographical** order.

For example, here are all valid 3 parentheses sequences in lexicographical order:

```
((()))

(()())

(())()

()(())

()()()

```

Given n and k, write an algorithm to give the k-th smallest sequence in **lexicographical** order.

For large data set: `1 ≤ n ≤ 100` and `1 ≤ k ≤ 10^18`