mod = 998244353 omega = pow(3,119,mod) rev_omega = pow(omega,mod-2,mod) N = 2*10**5 g1 = [1]*(N+1) # 元テーブル g2 = [1]*(N+1) #逆元テーブル inv = [1]*(N+1) #逆元テーブル計算用テーブル for i in range( 2, N + 1 ): g1[i]=( ( g1[i-1] * i ) % mod ) inv[i]=( ( -inv[mod % i] * (mod//i) ) % mod ) g2[i]=( (g2[i-1] * inv[i]) % mod ) inv[0]=0 def _ntt(f,L,reverse=False): F=[f[i] for i in range(L)] n = L.bit_length() - 1 base = omega if reverse: base = rev_omega if not n: return F size = 2**n wj = pow(base,2**22,mod) res = [0]*2**n for i in range(n,0,-1): use_omega = pow(base,2**(22+i-n),mod) res = [0]*2**n size //= 2 w = 1 for j in range(0,L//2,size): for a in range(size): res[a+j] = (F[a+2*j] + w * F[a+size+2*j]) % mod t = (w * wj) % mod res[L//2+a+j] = (F[a+2*j] + t * F[a+size+2*j]) % mod w = (w * use_omega) % mod F = res return res def ntt(f,L=0): l = len(f) if not L: L = 1<<((l-1).bit_length()) while len(f) c[i] = sum(a[j] * b[i - j] for j in range(i + 1)) % 998244353. It returns an empty list if at least one of a and b are empty. Constraints ----------- > len(a) + len(b) <= 8388609 Complexity ---------- > O(n log n), where n = len(a) + len(b). """ n = len(a) m = len(b) if n == 0 or m == 0: return [] if min(n, m) <= 0: return _convolution_naive(a, b) if a is b: return _convolution_square(a) return _convolution_fft(a, b) import sys,random,bisect from collections import deque,defaultdict from heapq import heapify,heappop,heappush from itertools import permutations from math import gcd,log input = lambda :sys.stdin.readline().rstrip() mi = lambda :map(int,input().split()) li = lambda :list(mi()) def Z_algorithm(s): N = len(s) Z_alg = [0]*N Z_alg[0] = N i = 1 j = 0 while i < N: while i+j < N and s[j] == s[i+j]: j += 1 Z_alg[i] = j if j == 0: i += 1 continue k = 1 while i+k < N and k + Z_alg[k]a以外にするとこがある(->?を置き換える部分がある) S[i:i+M] と S[j:j+M] (i < j) の置き換えを比較するとき、 i+M < j のとき、jが小さい S[i:j] に ? があった場合、jが小さい ない場合、S[j:i+M] を T[j-i:M] と T[:i+M-j] の比較 これで決着がつかない場合、iが小さい """ wild_cnt = [0] + [S[i]=="?" for i in range(N)] for i in range(N): wild_cnt[i+1] += wild_cnt[i] T_Z = Z_algorithm(T) def compare(i,j): if i+M <= j: return j cnt = wild_cnt[j-1] - wild_cnt[i-1] if cnt > 0: return j if T_Z[j-i]==M+i-j: return i if T[j-i+T_Z[j-i]] > T[T_Z[j-i]]: return j return i hash = [k+1 for k in range(26)] f = [0] * N for i in range(N): if S[i]!="?": f[i] = hash[ord(S[i])-ord("a")] g = [0] * M for i in range(M): if T[i]!="?": g[i] = hash[ord(T[i])-ord("a")] p = convolution([f[i]**3 % mod for i in range(N)],g[::-1]) q = convolution([f[i]**2 % mod for i in range(N)],[g[i]**2 % mod for i in range(M)][::-1]) r = convolution([f[i] % mod for i in range(N)],[g[i]**3 % mod for i in range(M)][::-1]) cand = [] for i in range(N-M+1): if (p[i+M-1]-2*q[i+M-1]+r[i+M-1]) % mod == 0: cand.append(i) if not cand: return -1 k = cand[0] for i in cand[1:]: k = compare(k,i) res = S[:k].replace("?","a") + T + S[k+M:].replace("?","a") return res for _ in range(int(input())): N,M = mi() S = input().rstrip() T = input().rstrip() print(solve(N,M,S,T))