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 翻译