問題文

はちじくんは，友人の誕生日にプレゼントとして英小文字からなる文字列 $S_1$ を用意して渡すことにしました．

友人を驚かせようと，はちじくんは文字列 $S_1$ を連続する部分列として文字列 $S_2$ を含むように作ろうとしました．しかし，はちじくんは，作ろうとした文字列の一部を忘れてしまいました．

英小文字と，? からなる長さ $N$ の文字列 $S_1$ が与えられ，? ははちじくんがその箇所の文字を忘れたことを表します．はちじくんのために，? を英小文字に置き換えて，連続する部分列として長さ $M$ の文字列 $S_2$ を含む文字列を復元してください．ただし，そのような文字列が複数ある場合には，その中で辞書順最小のものを求め，そのような文字列が無い場合はその旨を報告してください．

$T$ 個のテストケースが与えられるので，それぞれに対して答えを求めてください．

入力

入力は以下の形式で標準入力から与えられる．

$T$
$case_1$
$case_2$
$\vdots$
$case_T$

各ケースは以下の形式で与えられる．

$N$ $M$
$S_1$
$S_2$

制約

• $N, M, T$ は整数である．
• $1 \leq T \leq 10^5$
• $1 \leq M \leq N \leq 5 \times 10^5$
• $S_1$ は英小文字および ? のみからなる長さ $N$ の文字列である．
• $S_2$ は英小文字のみからなる長さ $M$ の文字列である．
• 1つの入力ファイルに対し，$N$ の総和は $5 \times 10^5$ を超えない．

出力

$T$ 行にわたって出力せよ．$i(1 \leq i \leq T)$ 行目には $i$ 番目のテストケースについて，$S_1$ のうち ? である箇所を英小文字に変えることで連続する部分列として $S_2$ を含むようにすることが不可能ならば，-1 を出力せよ．可能ならば，そのような文字列の中で辞書順最小のものを出力せよ．

サンプル

4
13 10
g?e??owo??d?d
helloworld
26 3
abcdefghijklmnopqrstuvwx??
zzz
10 10
helloworld
helloworld
12 3
t?t?r???g?s?
kog

ghelloworldad
-1
helloworld
tatarakogasa