공통 괄호 문자열 사전

(와 )만으로 이루어진 두 문자열 $A$, $B$와 자연수 $K$가 주어진다.

$A$의 부분 문자열이면서 $B$의 부분 문자열이고, 올바른 괄호열인 서로 다른 문자열들의 집합을 $S(A, B)$라고 하자.

$S(A, B)$의 크기가 $K$ 이상인지 판별하고, 크기가 $K$ 이상이라면 $S(A, B)$를 사전 순으로 정렬했을 때 $K$번째 문자열을 구하라.

하나의 입력 데이터에서 $T$개의 테스트 케이스를 해결해야 한다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다.

다음 $T$개의 각 줄에는 하나의 테스트 케이스가 주어진다. 두 문자열 $A$와 $B$, 자연수 $K$가 공백 하나씩을 사이에 두고 차례로 적혀 있다.

각 테스트 케이스마다 주어진 순서대로 한 줄에 답을 출력한다.

• $S(A, B)$의 크기가 $K$ 미만이면 -1을 출력한다.
• $S(A, B)$의 크기가 $K$ 이상이면 $S(A, B)$에서 사전 순 $K$번째 문자열을 출력한다.

• $1 \le T \le 500\,000$
• $A$와 $B$는 각각 여는 괄호와 닫는 괄호로만 이루어진 길이가 1 이상인 문자열이다.
• $1 \le K \le 10^{18}$
• $\sum |A| \le 500\,000$
• $\sum |B| \le 500\,000$

$\sum |A|$는 하나의 입력에서 주어지는 모든 $A$의 길이 합이고, $\sum |B|$는 하나의 입력에서 주어지는 모든 $B$의 길이 합이다.

올바른 괄호열의 정의

올바른 괄호열은 다음과 같이 정의한다.

• 한 쌍의 괄호로만 이루어진 문자열 ()는 올바른 괄호열이다.
• $X$가 올바른 괄호열이면, $X$를 괄호로 감싼 (X)도 올바른 괄호열이다.
• $X$와 $Y$가 올바른 괄호열이면, 두 문자열을 이어 붙인 $XY$도 올바른 괄호열이다.
• 모든 올바른 괄호열은 위 세 가지 규칙을 통해서만 만들어진다.

예를 들어 (()(()))와 (())()()는 올바른 괄호열이지만, (()와 )((()()은 올바른 괄호열이 아니다.

부분 문자열의 정의

길이가 $l$인 문자열 $s$와 $1 \le i \le j \le l$인 두 정수 $i$, $j$에 대해, $s[i..j]$는 $s$의 $i$번째 문자부터 $j$번째 문자까지를 순서대로 담은 문자열이다. 이런 문자열들을 $s$의 부분 문자열이라고 한다.

예를 들어 $s$가 ()(()()이면 $s[1..5]$는 (()이고, $s[1..7]$은 ()()이다. 따라서 (()과 ()()은 ()(()()의 부분 문자열이다. 하지만 )()(은 ()(()()의 부분 문자열이 아니다.

사전 순의 정의

길이가 $l_1$인 문자열 $s_1[1..l_1]$이 길이가 $l_2$인 문자열 $s_2[1..l_2]$보다 사전 순으로 앞선다는 것은 아래 두 조건 중 하나가 성립한다는 뜻이다.

• $s_1$이 $s_2$의 접두사이다. 즉 $l_1 < l_2$이고, 모든 $1 \le i \le l_1$에 대해 $s_1[i] = s_2[i]$이다.
• $1 \le i \le \min(l_1, l_2)$ 범위에서 $s_1[i] \ne s_2[i]$가 성립하는 가장 작은 $i$에 대해 $s_1[i] < s_2[i]$이다.

이 문제에서 여는 괄호 (는 닫는 괄호 )보다 사전에서 앞선 문자이다. 즉 ( < )이다.

이 방식은 C++, Java, Python에서 두 문자열을 비교하는 방식과 같다.