K번째 좋은 문자열

좋은 문자열은 다음과 같이 정의한다.

• 문자열 ()는 좋은 문자열이다.
• $S$가 좋은 문자열이면 (SS...S)도 좋은 문자열이다. 즉, 같은 좋은 문자열 하나를 한 번 이상 이어 붙인 뒤 전체를 괄호로 감싼 문자열은 좋은 문자열이다.
• 위의 두 경우를 제외하면 좋은 문자열은 없다.

문자열 $X$의 부분 수열은 $X$에서 문자를 0개 이상 지워서 얻은 문자열이다.

문자열 $S$가 주어진다. $S$의 각 문자는 ( 또는 )이다.

$S$의 부분 수열 중 좋은 문자열인 것을 서로 다른 것만 모은 집합을 $G$라고 하자. $G$는 집합이므로 같은 좋은 문자열이 부분 수열로 여러 번 나타나도 $G$에는 하나만 들어 있다. 예를 들어 $S$ = (()())이면 $G$에는 (), (()), (()())가 들어 있다.

$K$가 주어졌을 때 $G$에 들어 있는 문자열 중 사전 순으로 $K$번째인 문자열을 구하는 프로그램을 작성하시오. 순서는 1부터 센다. 사전 순으로 비교할 때 (는 )보다 앞선다.

첫째 줄에 문자열 $S$가 주어진다. $S$의 길이는 1 이상 150 이하이다.

둘째 줄에 정수 $K$가 주어진다. ($1 \le K \le 10^9$)

첫째 줄에 $G$에 들어 있는 문자열 중 사전 순으로 $K$번째 문자열을 출력한다. 그런 문자열이 없으면 -1을 출력한다.