← 返回题目列表

AtCoder · nupc2024_h

H. LCS订单

中文机器翻译题面 查看原题

配点 : 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 。