题目描述

给定两个只由左括号 ( 与右括号 ) 构成的字符串 $A$ 和 $B$，以及一个自然数 $K$。

我们定义集合 $S(A, B)$ 表示：所有既是字符串 $A$ 的子串、又是字符串 $B$ 的子串，并且是一个合法括号序列的不同字符串所组成的集合。

你的任务是判断 $S(A, B)$ 的大小是否不少于 $K$。如果不小于，则输出 $S(A, B)$ 中按字典序排列后的第 $K$ 个字符串；否则，输出 $-1$。

你需要在一个输入数据中处理 $T$ 个测试用例。

合法括号序列的定义

一个合法括号序列定义如下：

• 单个括号对构成的字符串 () 是合法括号序列。
• 若 $X$ 是合法括号序列，则 $(X)$ 也是合法括号序列。
• 若 $X$ 和 $Y$ 都是合法括号序列，则将它们连接而成的 $XY$ 也是合法括号序列。
• 所有合法括号序列都只能通过上述三条规则构造。

例如：((()(()))) 和 (())()() 是合法括号序列，而 (() 和 )((()() 都不是。

子串的定义

给定长度为 $l$ 的字符串 $s$ 和两个整数 $i, j$，其中 $1 \leq i \leq j \leq l$，则 $s[i..j]$ 表示从 $s$ 的第 $i$ 个字符到第 $j$ 个字符组成的子字符串。

例如若 $s = \texttt{()(()()}$，则 $s[1..5] = \texttt{(()(}$，$s[1..7] = \texttt{()(()()}$，因此 (()( 和 ()(()() 都是 $s$ 的子串。但 )()( 不是该字符串的子串。

字典序的定义

给定两个字符串 $s_1[1..l_1]$ 和 $s_2[1..l_2]$，我们说 $s_1$ 在字典序上早于 $s_2$，当且仅当满足以下任一条件：

• $s_1$ 是 $s_2$ 的前缀，且 $l_1 < l_2$
• 存在最小的 $i$ 满足 $s_1[i] \ne s_2[i]$ 且 $s_1[i] < s_2[i]$

在本题中，左括号 '(' 比右括号 ')' 更小，即 '(' < ')'。这与 C++、Java 和 Python 中的字符串比较方式一致。

输入格式

第一行包含一个整数 $T$，表示测试用例的个数。

接下来的 $T$ 行中，每行描述一个测试用例，包含字符串 $A$、字符串 $B$ 和整数 $K$，它们之间用一个空格隔开。

输出格式

对于每个测试用例，按输入顺序依次输出一行：

• 若 $|S(A, B)| < K$，输出 $-1$
• 否则，输出 $S(A, B)$ 中字典序第 $K$ 小的字符串

输入输出样例 #1

输入 #1

3
()((())) (()((())))() 3
))(()(((( )())))))( 1
())) )))))(()) 4

输出 #1

()
()
-1

说明/提示

约束条件

设 $\sum |A|$ 表示一个输入数据中所有测试用例的字符串 $A$ 的总长度之和，$\sum |B|$ 类似。

• $1 \leq T \leq 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| \leq 100$，$\sum |B| \leq 100$
2. （11 分）$\sum |A| \leq 1\,000$，$\sum |B| \leq 1\,000$
3. （16 分）$\sum |A| \leq 10\,000$，$\sum |B| \leq 10\,000$，且 $A = B$，$K = 1$
4. （25 分）$\sum |A| \leq 10\,000$，$\sum |B| \leq 10\,000$
5. （10 分）$A = B$，$K = 1$
6. （12 分）$A = B$
7. （9 分）$K = 1$
8. （13 分）无额外约束条件