공통 괄호 문자열 사전

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

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

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

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

올바른 괄호열의 정의

올바른 괄호열이란 다음과 같이 정의된다.

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

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

부분문자열의 정의

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

예를 들어 $ s $가 ()(()()이라면, $ s[3..5] $는 (()이고, $ s[4..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] $이다.
• $ s_1[i] \neq s_2[i] $가 성립하는 가장 작은 $ i $ ($ 1 \le i \le \min(l_1, l_2) $)에 대해 $ s_1[i] < s_2[i] $이다.

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

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

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

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

1. (4점) $ \sum |A| \le 100 $, $ \sum |B| \leq 100 $
2. (11점) $ \sum |A| \le 1\,000 $, $ \sum |B| \leq 1\,000 $
3. (16점) $ \sum |A| \le 10\,000 $, $ \sum |B| \leq 10\,000 $, $ A = B $, $ K = 1 $
4. (25점) $ \sum |A| \le 10\,000 $, $ \sum |B| \leq 10\,000 $
5. (10점) $ A = B $, $ K = 1 $
6. (12점) $ A = B $
7. (9점) $ K = 1 $
8. (13점) 추가 제약 조건 없음.

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

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

각각의 테스트 케이스마다, 주어진 순서대로, 한 개의 줄에,

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