問題一覧 > 通常問題

No.2231 Surprising Flash!

レベル : / AI推定難易度 : 2400 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 16
作問者 : 👑 AngrySadEight / テスター : akakimidori
お気に入りにしたユーザー ProblemId : 9157 / 自分の提出
問題文最終更新日: 2023-02-18 12:57:06
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 378 (順位表) の他の問題:

Problem Statement

Hachiji-kun has decided to prepare a string $S_1$ consisting of lowercase English letters and give it to a friend as a birthday present.

To surprise the friend, Hachiji-kun tried to make the string $S_1$ so that it contains the string $S_2$ as a contiguous substring. However, Hachiji-kun has forgotten part of the string he was trying to make.

You are given a string $S_1$ of length $N$ consisting of lowercase English letters and ?, where ? indicates that Hachiji-kun has forgotten the character at that position. For Hachiji-kun, replace each ? with a lowercase English letter to restore a string that contains the string $S_2$ of length $M$ as a contiguous substring. If there are multiple such strings, find the lexicographically smallest one among them; if there is no such string, report that.

You are given $T$ test cases; find the answer for each of them.

Input

The input is given from standard input in the following format.

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

Each case is given in the following format.

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

Constraints

  • $N, M, T$ are integers.
  • $1 \leq T \leq 10^5$
  • $1 \leq M \leq N \leq 5 \times 10^5$
  • $S_1$ is a string of length $N$ consisting only of lowercase English letters and ?.
  • $S_2$ is a string of length $M$ consisting only of lowercase English letters.
  • For a single input file, the sum of $N$ does not exceed $5 \times 10^5$.

Output

Output over $T$ lines. On the $i(1 \leq i \leq T)$-th line, for the $i$-th test case, output -1 if it is impossible to make the string contain $S_2$ as a contiguous substring by changing the ? positions of $S_1$ to lowercase English letters. If it is possible, output the lexicographically smallest such string.

Sample

Sample 1
Input
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
Output
ghelloworldad
-1
helloworld
tatarakogasa

For the first test case, the $2$-nd through $11$-th characters form helloworld, so the string indeed contains helloworld as a contiguous substring. Other strings such as ghelloworldld also contain helloworld as a contiguous substring, but note that you must output the lexicographically smallest one.

For the second test case, no matter which characters the $2$ occurrences of ? are changed to, the string cannot be made to contain zzz as a contiguous substring.

For the third test case, helloworld itself contains helloworld as a contiguous substring.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。