P12727 [KOI 2021 Round 2] 公共括号子串字典序

试题来源：。中文翻译做了少量本土化修改。 按照[署名—非商业性使用—相同方式共享 4.0 协议国际版](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh-hans)进行授权。

给定两个只由左括号 `(` 与右括号 `)` 构成的字符串 $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$ 小的字符串

**约束条件** 设 $\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 分）无额外约束条件