AT_nupc2024_h LCS order

長さ $ 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 $ 個以上の文字を取り出し、それらを順序を変えずに並べた文字列のことを指します。

入力は以下の形式で標準入力から与えられます。 > $ N $ $ M $ $ S $ $ T $ $ Q $ $ k_1 $ $ k_2 $ $ \vdots $ $ k_Q $

$ Q $ 行出力してください。 $ i \ (1\leq i\leq Q) $ 行目には、 $ i $ 番目のクエリの答えを出力してください。

### Sample Explanation 1 LCS の長さは $ 3 $ であり、辞書順にすべて列挙すると、`abc`, `abd`, `abe`, `abf`となります。 したがって、 $ 3 $ 番目のクエリまでは $ 1, 2, 4 $ 番の LCS を出力します。 $ 4 $ 番目のクエリでは、LCS の数は全部で $ 4 $ 種類であるため `-1` を出力します。 ### Sample Explanation 2 LCS の長さは $ 2 $ であり、辞書順にすべて列挙すると、`ab` のみとなります。(取る添え字が異なるものは区別しません。) ### Sample Explanation 3 二つの文字列で一致する箇所はなく、LCS は空文字列となるため `-1` を出力します。 ### Constraints - $ 1\leq N,M,Q\leq 1000 $ - $ 1\leq k_i\leq 10^9 $ - $ N,M,Q,k_i $ は整数 - $ S $ は長さ $ N $ の英小文字列 - $ T $ は長さ $ M $ の英小文字列