問題文

長さ N の文字列 S と、長さ M の文字列 T が与えられます。

以下の Q 個のクエリに答えてください。

i \ (1\leq i\leq Q) 番目のクエリは以下の通りです。

• S, T の LCS のうち、辞書順で k_i 番目のものを出力する。

ただし、該当する LCS が存在しない場合や空文字列である場合は、-1 を出力してください。

なお、LCS 同士が文字列として等しい場合、異なる位置から取り出したものであっても、それらは区別しないものとします。

制約

• 1\leq N,M,Q\leq 1000
• 1\leq k_i\leq 10^9
• N,M,Q,k_i は整数
• S は長さ N の英小文字列
• T は長さ M の英小文字列

入力例1

6 6
abcdef
abfedc
4
1
2
4
8

出力例1

abc
abd
abf
-1

LCS の長さは 3 であり、辞書順にすべて列挙すると、abc, abd, abe, abfとなります。

したがって、 3 番目のクエリまでは 1, 2, 4 番の LCS を出力します。

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 を出力します。