配点 : 100 点
問題文
长度 小于或等于 N 的字符串 S 和长度 M 的字符串 T 。 对于
下面 Q 询问。
i \ (1\leq i\leq Q) 个查询如下。
- S, T 的LCS中,按字典顺序排列: 输出第 k_i 项。
但是,如果对应的LCS不存在或者为空字符串,-1 。
须满足
如果LCS是同一个字符串,即使从不同位置提取也无法区分。
什么是LCS(最长公共子序列)?
文字列 S, T 的 LCS 是什么?S 的偶数子序列 它指的是最长的字符串,也是 T 的子字符串。 这里,一个字符串 U 的子序列是 指由U 减去 0 或更多字符按相同顺序排列的字符串。制約
- 1\leq N,M,Q\leq 1000
- 1\leq k_i\leq 10^9
- N,M,Q,k_i 是一个整数
- S 是长度, 请以 N 小写字符串 请输出
- T 是长度, 请以 M 小写字符串 请输出
入力
输入是按以下格式从标准输入给出的。
N M S T Q k_1 k_2 \vdots k_Q
出力
Q 行。 列出
i \ (1\leq i\leq Q) 行中,i 个查询的答案。
入力例1
6 6 abcdef abfedc 4 1 2 4 8
出力例1
abc abd abf -1
LCS 长度为 3 ,并按字典顺序枚举它们:abc, abd, abe, abf。
对于
因此, 3 次查询 输出 LCS 编号为 1, 2, 4 。 在第
4 次查询中,LCS 总数为 4 因为它是类型
仅 -1 。
入力例2
5 5 abcde abbbb 2 1 2
出力例2
ab -1
LCS 长度为 2 ,并按字典顺序枚举它们:ab 。 (下标不同者不区分。)
入力例3
4 4 abcd efgh 1 1
出力例3
-1
两个字符串之间没有匹配项,LCS 将为空字符串。 -1 。