AT_nupc2024_h.LCS order

给定一个长度为 $N$ 的字符串 $S$ 和一个长度为 $M$ 的字符串 $T$。

请回答以下 $Q$ 个查询。

第 $i \ (1\leq i\leq Q)$ 个查询如下：

• 输出 $S, T$ 的所有 LCS（最长公共子序列）中字典序第 $k_i$ 小的一个。

如果不存在对应的 LCS，或者 LCS 是空字符串，则输出 -1。

注意，如果 LCS 作为字符串完全相同，不论它们是从不同位置取的，都视为相同的一个子序列。

LCS（Longest Common Subsequence，最长公共子序列）指的是，既是字符串 $S$ 的子序列、又是字符串 $T$ 的子序列中长度最大的字符串。这里，字符串 $U$ 的“子序列”是指，从 $U$ 中选取 $0$ 个或多个字符，并保持原有的顺序排列所得到的字符串。

输入以如下格式由标准输入给出。

$N$ $M$ $S$ $T$ $Q$ $k_1$ $k_2$ $\vdots$ $k_Q$

请输出 $Q$ 行。

第 $i\ (1\leq i\leq Q)$ 行输出第 $i$ 个查询的答案。

样例解释 1

LCS 的长度为 $3$，按字典序全部列举为：abc、abd、abe、abf。

因此，对于前三个查询，输出第 $1, 2, 4$ 个 LCS。

第 $4$ 个查询时，LCS 总数仅为 $4$ 种，因此需输出 -1。

样例解释 2

LCS 的长度为 $2$，按字典序全部列举只有一个：ab。（不同的取法下标不作区分。）

样例解释 3

两个字符串没有任何匹配字符，LCS 是空字符串，因此输出 -1。

数据范围

• $1\leq N,M,Q\leq 1000$
• $1\leq k_i\leq 10^9$
• $N,M,Q,k_i$ 均为整数
• $S$ 是长度 $N$ 的小写英文字母字符串
• $T$ 是长度 $M$ 的小写英文字母字符串

由 ChatGPT 5 翻译