K-th good string

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 ).

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$).

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