K-th good string

Time limit2sMemory limit512 MB

Summary

Given a bracket string S, list the distinct good strings that appear as subsequences in lexicographic order and print the K-th one.

Level: Hard8 of 10
Topics: Dynamic programming, String, Combinatorics
Solved: No attempts yet

Problem

Good strings are defined as follows.

The string () is a good string.
If $S$ is a good string, then (SS...S) is also a good string. In other words, if you write one good string one or more times in a row and wrap the whole result in parentheses, you get a good string.
No other string is a good string.

A subsequence of a string $X$ is a string obtained by deleting zero or more characters from $X$ .

You are given a string $S$ . Each character of $S$ is ( or ).

Let $G$ be the set of distinct good strings that are subsequences of $S$ . Because $G$ is a set, a good string that occurs as a subsequence several times is contained in $G$ only once. For example, if $S$ = (()()), then $G$ contains (), (()), and (()()).

Given $K$ , write a program that finds the $K$ -th string of $G$ in lexicographic order. Indexing starts at 1. In lexicographic comparison, ( comes before ).

Input

The first line contains the string $S$ . The length of $S$ is between 1 and 150, inclusive.

The second line contains the integer $K$ ( $1 \le K \le 10^9$ ).

Output

Print the $K$ -th string of $G$ in lexicographic order. If no such string exists, print -1.

Examples5

Example 1
Input
```
()))((()())
3
```
Expected output
```
(())
```
Example 2
Input
```
))))))))))))((((((((((
1
```
Expected output
```
-1
```
Example 3
Input
```
(())(()(()))
1
```
Expected output
```
(((())))
```
Example 4
Input
```
(())))()((())())
8
```
Expected output
```
()
```
Example 5
Input
```
(
1000000000
```
Expected output
```
-1
```