結果
問題 | No.2231 Surprising Flash! |
ユーザー |
|
提出日時 | 2023-02-24 22:18:00 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
RE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 32,981 bytes |
コンパイル時間 | 4,306 ms |
コンパイル使用メモリ | 320,968 KB |
最終ジャッジ日時 | 2025-02-10 21:21:26 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 43 RE * 1 |
ソースコード
/*** date : 2023-02-24 22:17:53*/#define NDEBUGusing namespace std;// intrinstic#include <immintrin.h>#include <algorithm>#include <array>#include <bitset>#include <cassert>#include <cctype>#include <cfenv>#include <cfloat>#include <chrono>#include <cinttypes>#include <climits>#include <cmath>#include <complex>#include <cstdarg>#include <cstddef>#include <cstdint>#include <cstdio>#include <cstdlib>#include <cstring>#include <deque>#include <fstream>#include <functional>#include <initializer_list>#include <iomanip>#include <ios>#include <iostream>#include <istream>#include <iterator>#include <limits>#include <list>#include <map>#include <memory>#include <new>#include <numeric>#include <ostream>#include <queue>#include <random>#include <set>#include <sstream>#include <stack>#include <streambuf>#include <string>#include <tuple>#include <type_traits>#include <typeinfo>#include <unordered_map>#include <unordered_set>#include <utility>#include <vector>// utilitynamespace Nyaan {using ll = long long;using i64 = long long;using u64 = unsigned long long;using i128 = __int128_t;using u128 = __uint128_t;template <typename T>using V = vector<T>;template <typename T>using VV = vector<vector<T>>;using vi = vector<int>;using vl = vector<long long>;using vd = V<double>;using vs = V<string>;using vvi = vector<vector<int>>;using vvl = vector<vector<long long>>;template <typename T, typename U>struct P : pair<T, U> {template <typename... Args>P(Args... args) : pair<T, U>(args...) {}using pair<T, U>::first;using pair<T, U>::second;P &operator+=(const P &r) {first += r.first;second += r.second;return *this;}P &operator-=(const P &r) {first -= r.first;second -= r.second;return *this;}P &operator*=(const P &r) {first *= r.first;second *= r.second;return *this;}template <typename S>P &operator*=(const S &r) {first *= r, second *= r;return *this;}P operator+(const P &r) const { return P(*this) += r; }P operator-(const P &r) const { return P(*this) -= r; }P operator*(const P &r) const { return P(*this) *= r; }template <typename S>P operator*(const S &r) const {return P(*this) *= r;}P operator-() const { return P{-first, -second}; }};using pl = P<ll, ll>;using pi = P<int, int>;using vp = V<pl>;constexpr int inf = 1001001001;constexpr long long infLL = 4004004004004004004LL;template <typename T>int sz(const T &t) {return t.size();}template <typename T, typename U>inline bool amin(T &x, U y) {return (y < x) ? (x = y, true) : false;}template <typename T, typename U>inline bool amax(T &x, U y) {return (x < y) ? (x = y, true) : false;}template <typename T>inline T Max(const vector<T> &v) {return *max_element(begin(v), end(v));}template <typename T>inline T Min(const vector<T> &v) {return *min_element(begin(v), end(v));}template <typename T>inline long long Sum(const vector<T> &v) {return accumulate(begin(v), end(v), 0LL);}template <typename T>int lb(const vector<T> &v, const T &a) {return lower_bound(begin(v), end(v), a) - begin(v);}template <typename T>int ub(const vector<T> &v, const T &a) {return upper_bound(begin(v), end(v), a) - begin(v);}constexpr long long TEN(int n) {long long ret = 1, x = 10;for (; n; x *= x, n >>= 1) ret *= (n & 1 ? x : 1);return ret;}template <typename T, typename U>pair<T, U> mkp(const T &t, const U &u) {return make_pair(t, u);}template <typename T>vector<T> mkrui(const vector<T> &v, bool rev = false) {vector<T> ret(v.size() + 1);if (rev) {for (int i = int(v.size()) - 1; i >= 0; i--) ret[i] = v[i] + ret[i + 1];} else {for (int i = 0; i < int(v.size()); i++) ret[i + 1] = ret[i] + v[i];}return ret;};template <typename T>vector<T> mkuni(const vector<T> &v) {vector<T> ret(v);sort(ret.begin(), ret.end());ret.erase(unique(ret.begin(), ret.end()), ret.end());return ret;}template <typename F>vector<int> mkord(int N,F f) {vector<int> ord(N);iota(begin(ord), end(ord), 0);sort(begin(ord), end(ord), f);return ord;}template <typename T>vector<int> mkinv(vector<T> &v) {int max_val = *max_element(begin(v), end(v));vector<int> inv(max_val + 1, -1);for (int i = 0; i < (int)v.size(); i++) inv[v[i]] = i;return inv;}vector<int> mkiota(int n) {vector<int> ret(n);iota(begin(ret), end(ret), 0);return ret;}template <typename T>T mkrev(const T &v) {T w{v};reverse(begin(w), end(w));return w;}template <typename T>bool nxp(vector<T> &v) {return next_permutation(begin(v), end(v));}template <typename T>using minpq = priority_queue<T, vector<T>, greater<T>>;} // namespace Nyaan// bit operationnamespace Nyaan {__attribute__((target("popcnt"))) inline int popcnt(const u64 &a) {return _mm_popcnt_u64(a);}inline int lsb(const u64 &a) { return a ? __builtin_ctzll(a) : 64; }inline int ctz(const u64 &a) { return a ? __builtin_ctzll(a) : 64; }inline int msb(const u64 &a) { return a ? 63 - __builtin_clzll(a) : -1; }template <typename T>inline int gbit(const T &a, int i) {return (a >> i) & 1;}template <typename T>inline void sbit(T &a, int i, bool b) {if (gbit(a, i) != b) a ^= T(1) << i;}constexpr long long PW(int n) { return 1LL << n; }constexpr long long MSK(int n) { return (1LL << n) - 1; }} // namespace Nyaan// inoutnamespace Nyaan {template <typename T, typename U>ostream &operator<<(ostream &os, const pair<T, U> &p) {os << p.first << " " << p.second;return os;}template <typename T, typename U>istream &operator>>(istream &is, pair<T, U> &p) {is >> p.first >> p.second;return is;}template <typename T>ostream &operator<<(ostream &os, const vector<T> &v) {int s = (int)v.size();for (int i = 0; i < s; i++) os << (i ? " " : "") << v[i];return os;}template <typename T>istream &operator>>(istream &is, vector<T> &v) {for (auto &x : v) is >> x;return is;}istream &operator>>(istream &is, __int128_t &x) {string S;is >> S;x = 0;int flag = 0;for (auto &c : S) {if (c == '-') {flag = true;continue;}x *= 10;x += c - '0';}if (flag) x = -x;return is;}istream &operator>>(istream &is, __uint128_t &x) {string S;is >> S;x = 0;for (auto &c : S) {x *= 10;x += c - '0';}return is;}ostream &operator<<(ostream &os, __int128_t x) {if (x == 0) return os << 0;if (x < 0) os << '-', x = -x;string S;while (x) S.push_back('0' + x % 10), x /= 10;reverse(begin(S), end(S));return os << S;}ostream &operator<<(ostream &os, __uint128_t x) {if (x == 0) return os << 0;string S;while (x) S.push_back('0' + x % 10), x /= 10;reverse(begin(S), end(S));return os << S;}void in() {}template <typename T, class... U>void in(T &t, U &...u) {cin >> t;in(u...);}void out() { cout << "\n"; }template <typename T, class... U, char sep = ' '>void out(const T &t, const U &...u) {cout << t;if (sizeof...(u)) cout << sep;out(u...);}void outr() {}template <typename T, class... U, char sep = ' '>void outr(const T &t, const U &...u) {cout << t;outr(u...);}struct IoSetupNya {IoSetupNya() {cin.tie(nullptr);ios::sync_with_stdio(false);cout << fixed << setprecision(15);cerr << fixed << setprecision(7);}} iosetupnya;} // namespace Nyaan// debug#ifdef NyaanDebug#define trc(...) (void(0))#else#define trc(...) (void(0))#endif#ifdef NyaanLocal#define trc2(...) (void(0))#else#define trc2(...) (void(0))#endif// macro#define each(x, v) for (auto&& x : v)#define each2(x, y, v) for (auto&& [x, y] : v)#define all(v) (v).begin(), (v).end()#define rep(i, N) for (long long i = 0; i < (long long)(N); i++)#define repr(i, N) for (long long i = (long long)(N)-1; i >= 0; i--)#define rep1(i, N) for (long long i = 1; i <= (long long)(N); i++)#define repr1(i, N) for (long long i = (N); (long long)(i) > 0; i--)#define reg(i, a, b) for (long long i = (a); i < (b); i++)#define regr(i, a, b) for (long long i = (b)-1; i >= (a); i--)#define fi first#define se second#define ini(...) \int __VA_ARGS__; \in(__VA_ARGS__)#define inl(...) \long long __VA_ARGS__; \in(__VA_ARGS__)#define ins(...) \string __VA_ARGS__; \in(__VA_ARGS__)#define in2(s, t) \for (int i = 0; i < (int)s.size(); i++) { \in(s[i], t[i]); \}#define in3(s, t, u) \for (int i = 0; i < (int)s.size(); i++) { \in(s[i], t[i], u[i]); \}#define in4(s, t, u, v) \for (int i = 0; i < (int)s.size(); i++) { \in(s[i], t[i], u[i], v[i]); \}#define die(...) \do { \Nyaan::out(__VA_ARGS__); \return; \} while (0)namespace Nyaan {void solve();}int main() { Nyaan::solve(); }//namespace atcoder {namespace internal {std::vector<int> sa_naive(const std::vector<int>& s) {int n = int(s.size());std::vector<int> sa(n);std::iota(sa.begin(), sa.end(), 0);std::sort(sa.begin(), sa.end(), [&](int l, int r) {if (l == r) return false;while (l < n && r < n) {if (s[l] != s[r]) return s[l] < s[r];l++;r++;}return l == n;});return sa;}std::vector<int> sa_doubling(const std::vector<int>& s) {int n = int(s.size());std::vector<int> sa(n), rnk = s, tmp(n);std::iota(sa.begin(), sa.end(), 0);for (int k = 1; k < n; k *= 2) {auto cmp = [&](int x, int y) {if (rnk[x] != rnk[y]) return rnk[x] < rnk[y];int rx = x + k < n ? rnk[x + k] : -1;int ry = y + k < n ? rnk[y + k] : -1;return rx < ry;};std::sort(sa.begin(), sa.end(), cmp);tmp[sa[0]] = 0;for (int i = 1; i < n; i++) {tmp[sa[i]] = tmp[sa[i - 1]] + (cmp(sa[i - 1], sa[i]) ? 1 : 0);}std::swap(tmp, rnk);}return sa;}// SA-IS, linear-time suffix array construction// Reference:// G. Nong, S. Zhang, and W. H. Chan,// Two Efficient Algorithms for Linear Time Suffix Array Constructiontemplate <int THRESHOLD_NAIVE = 10, int THRESHOLD_DOUBLING = 40>std::vector<int> sa_is(const std::vector<int>& s, int upper) {int n = int(s.size());if (n == 0) return {};if (n == 1) return {0};if (n == 2) {if (s[0] < s[1]) {return {0, 1};} else {return {1, 0};}}if (n < THRESHOLD_NAIVE) {return sa_naive(s);}if (n < THRESHOLD_DOUBLING) {return sa_doubling(s);}std::vector<int> sa(n);std::vector<bool> ls(n);for (int i = n - 2; i >= 0; i--) {ls[i] = (s[i] == s[i + 1]) ? ls[i + 1] : (s[i] < s[i + 1]);}std::vector<int> sum_l(upper + 1), sum_s(upper + 1);for (int i = 0; i < n; i++) {if (!ls[i]) {sum_s[s[i]]++;} else {sum_l[s[i] + 1]++;}}for (int i = 0; i <= upper; i++) {sum_s[i] += sum_l[i];if (i < upper) sum_l[i + 1] += sum_s[i];}auto induce = [&](const std::vector<int>& lms) {std::fill(sa.begin(), sa.end(), -1);std::vector<int> buf(upper + 1);std::copy(sum_s.begin(), sum_s.end(), buf.begin());for (auto d : lms) {if (d == n) continue;sa[buf[s[d]]++] = d;}std::copy(sum_l.begin(), sum_l.end(), buf.begin());sa[buf[s[n - 1]]++] = n - 1;for (int i = 0; i < n; i++) {int v = sa[i];if (v >= 1 && !ls[v - 1]) {sa[buf[s[v - 1]]++] = v - 1;}}std::copy(sum_l.begin(), sum_l.end(), buf.begin());for (int i = n - 1; i >= 0; i--) {int v = sa[i];if (v >= 1 && ls[v - 1]) {sa[--buf[s[v - 1] + 1]] = v - 1;}}};std::vector<int> lms_map(n + 1, -1);int m = 0;for (int i = 1; i < n; i++) {if (!ls[i - 1] && ls[i]) {lms_map[i] = m++;}}std::vector<int> lms;lms.reserve(m);for (int i = 1; i < n; i++) {if (!ls[i - 1] && ls[i]) {lms.push_back(i);}}induce(lms);if (m) {std::vector<int> sorted_lms;sorted_lms.reserve(m);for (int v : sa) {if (lms_map[v] != -1) sorted_lms.push_back(v);}std::vector<int> rec_s(m);int rec_upper = 0;rec_s[lms_map[sorted_lms[0]]] = 0;for (int i = 1; i < m; i++) {int l = sorted_lms[i - 1], r = sorted_lms[i];int end_l = (lms_map[l] + 1 < m) ? lms[lms_map[l] + 1] : n;int end_r = (lms_map[r] + 1 < m) ? lms[lms_map[r] + 1] : n;bool same = true;if (end_l - l != end_r - r) {same = false;} else {while (l < end_l) {if (s[l] != s[r]) {break;}l++;r++;}if (l == n || s[l] != s[r]) same = false;}if (!same) rec_upper++;rec_s[lms_map[sorted_lms[i]]] = rec_upper;}auto rec_sa =sa_is<THRESHOLD_NAIVE, THRESHOLD_DOUBLING>(rec_s, rec_upper);for (int i = 0; i < m; i++) {sorted_lms[i] = lms[rec_sa[i]];}induce(sorted_lms);}return sa;}} // namespace internalstd::vector<int> suffix_array(const std::vector<int>& s, int upper) {assert(0 <= upper);for (int d : s) {assert(0 <= d && d <= upper);}auto sa = internal::sa_is(s, upper);return sa;}template <class T> std::vector<int> suffix_array(const std::vector<T>& s) {int n = int(s.size());std::vector<int> idx(n);iota(idx.begin(), idx.end(), 0);sort(idx.begin(), idx.end(), [&](int l, int r) { return s[l] < s[r]; });std::vector<int> s2(n);int now = 0;for (int i = 0; i < n; i++) {if (i && s[idx[i - 1]] != s[idx[i]]) now++;s2[idx[i]] = now;}return internal::sa_is(s2, now);}std::vector<int> suffix_array(const std::string& s) {int n = int(s.size());std::vector<int> s2(n);for (int i = 0; i < n; i++) {s2[i] = s[i];}return internal::sa_is(s2, 255);}// Reference:// T. Kasai, G. Lee, H. Arimura, S. Arikawa, and K. Park,// Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its// Applicationstemplate <class T>std::vector<int> lcp_array(const std::vector<T>& s,const std::vector<int>& sa) {int n = int(s.size());assert(n >= 1);std::vector<int> rnk(n);for (int i = 0; i < n; i++) {rnk[sa[i]] = i;}std::vector<int> lcp(n - 1);int h = 0;for (int i = 0; i < n; i++) {if (h > 0) h--;if (rnk[i] == 0) continue;int j = sa[rnk[i] - 1];for (; j + h < n && i + h < n; h++) {if (s[j + h] != s[i + h]) break;}lcp[rnk[i] - 1] = h;}return lcp;}std::vector<int> lcp_array(const std::string& s, const std::vector<int>& sa) {int n = int(s.size());std::vector<int> s2(n);for (int i = 0; i < n; i++) {s2[i] = s[i];}return lcp_array(s2, sa);}// Reference:// D. Gusfield,// Algorithms on Strings, Trees, and Sequences: Computer Science and// Computational Biologytemplate <class T> std::vector<int> z_algorithm(const std::vector<T>& s) {int n = int(s.size());if (n == 0) return {};std::vector<int> z(n);z[0] = 0;for (int i = 1, j = 0; i < n; i++) {int& k = z[i];k = (j + z[j] <= i) ? 0 : std::min(j + z[j] - i, z[i - j]);while (i + k < n && s[k] == s[i + k]) k++;if (j + z[j] < i + z[i]) j = i;}z[0] = n;return z;}std::vector<int> z_algorithm(const std::string& s) {int n = int(s.size());std::vector<int> s2(n);for (int i = 0; i < n; i++) {s2[i] = s[i];}return z_algorithm(s2);}} // namespace atcoderusing namespace std;template <typename T>struct SparseTable {inline static constexpr T INF = numeric_limits<T>::max() / 2;int N;vector<vector<T> > table;T f(T a, T b) { return min(a, b); }SparseTable() {}SparseTable(const vector<T> &v) : N(v.size()) {int b = 1;while ((1 << b) <= N) ++b;table.push_back(v);for (int i = 1; i < b; i++) {table.push_back(vector<T>(N, INF));for (int j = 0; j + (1 << i) <= N; j++) {table[i][j] = f(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);}}}// [l, r)T query(int l, int r) {assert(0 <= l and l <= r and r <= N);if (l == r) return INF;int b = 31 - __builtin_clz(r - l);return f(table[b][l], table[b][r - (1 << b)]);}};/*** @brief Sparse Table*/struct StringSearch {const string& S;int N;vector<int> sa, la, invsa;SparseTable<int> sparse;StringSearch(const string& _s) : S(_s), N(S.size()) {sa = atcoder::suffix_array(S);la = atcoder::lcp_array(S, sa);invsa.resize(N);for (int i = 0; i < N; i++) invsa[sa[i]] = i;sparse = SparseTable<int>{la};}// lcp(s[i, N), s[j, N))int lcp(int i, int j) {assert(0 <= min(i, j) and max(i, j) < N);if (i == j) return N - i;int x = min(invsa[i], invsa[j]);int y = max(invsa[i], invsa[j]);return sparse.query(x, y);}// lcp(s[a, b), s[c, d))int lcp(int a, int b, int c, int d) {assert(0 <= a and a <= b and b <= N);assert(0 <= c and c <= d and d <= N);int l = lcp(a, c);return min({l, b - a, d - c});}// lcp(s[a, b), s[c, d))template <typename Int>int lcp(pair<Int, Int> p, pair<Int, Int> q) {return lcp(p.first, p.second, q.first, q.second);}// s[i, N) > s[j, N) : 1// s[i, N) = s[j, N) : 0// s[i, N) < s[j, N) : -1int strcmp(int i, int j) {assert(0 <= min(i, j) and max(i, j) < N);if (i == j) return 0;return invsa[i] < invsa[j] ? -1 : 1;}// s[a, b) > s[c, d) : 1// s[a, b) = s[c, d) : 0// s[a, b) < s[c, d) : -1int strcmp(int a, int b, int c, int d) {int l = lcp(a, b, c, d);return a + l == b ? (c + l == d ? 0 : -1): c + l == d ? 1: S[a + l] < S[c + l] ? -1: 1;}// s[a, b) > s[c, d) : 1// s[a, b) = s[c, d) : 0// s[a, b) < s[c, d) : -1template <typename Int>int strcmp(pair<Int, Int> p, pair<Int, Int> q) {return strcmp(p.first, p.second, q.first, q.second);}};//template <uint32_t mod>struct LazyMontgomeryModInt {using mint = LazyMontgomeryModInt;using i32 = int32_t;using u32 = uint32_t;using u64 = uint64_t;static constexpr u32 get_r() {u32 ret = mod;for (i32 i = 0; i < 4; ++i) ret *= 2 - mod * ret;return ret;}static constexpr u32 r = get_r();static constexpr u32 n2 = -u64(mod) % mod;static_assert(r * mod == 1, "invalid, r * mod != 1");static_assert(mod < (1 << 30), "invalid, mod >= 2 ^ 30");static_assert((mod & 1) == 1, "invalid, mod % 2 == 0");u32 a;constexpr LazyMontgomeryModInt() : a(0) {}constexpr LazyMontgomeryModInt(const int64_t &b): a(reduce(u64(b % mod + mod) * n2)){};static constexpr u32 reduce(const u64 &b) {return (b + u64(u32(b) * u32(-r)) * mod) >> 32;}constexpr mint &operator+=(const mint &b) {if (i32(a += b.a - 2 * mod) < 0) a += 2 * mod;return *this;}constexpr mint &operator-=(const mint &b) {if (i32(a -= b.a) < 0) a += 2 * mod;return *this;}constexpr mint &operator*=(const mint &b) {a = reduce(u64(a) * b.a);return *this;}constexpr mint &operator/=(const mint &b) {*this *= b.inverse();return *this;}constexpr mint operator+(const mint &b) const { return mint(*this) += b; }constexpr mint operator-(const mint &b) const { return mint(*this) -= b; }constexpr mint operator*(const mint &b) const { return mint(*this) *= b; }constexpr mint operator/(const mint &b) const { return mint(*this) /= b; }constexpr bool operator==(const mint &b) const {return (a >= mod ? a - mod : a) == (b.a >= mod ? b.a - mod : b.a);}constexpr bool operator!=(const mint &b) const {return (a >= mod ? a - mod : a) != (b.a >= mod ? b.a - mod : b.a);}constexpr mint operator-() const { return mint() - mint(*this); }constexpr mint pow(u64 n) const {mint ret(1), mul(*this);while (n > 0) {if (n & 1) ret *= mul;mul *= mul;n >>= 1;}return ret;}constexpr mint inverse() const { return pow(mod - 2); }friend ostream &operator<<(ostream &os, const mint &b) {return os << b.get();}friend istream &operator>>(istream &is, mint &b) {int64_t t;is >> t;b = LazyMontgomeryModInt<mod>(t);return (is);}constexpr u32 get() const {u32 ret = reduce(a);return ret >= mod ? ret - mod : ret;}static constexpr u32 get_mod() { return mod; }};template <typename mint>struct NTT {static constexpr uint32_t get_pr() {uint32_t _mod = mint::get_mod();using u64 = uint64_t;u64 ds[32] = {};int idx = 0;u64 m = _mod - 1;for (u64 i = 2; i * i <= m; ++i) {if (m % i == 0) {ds[idx++] = i;while (m % i == 0) m /= i;}}if (m != 1) ds[idx++] = m;uint32_t _pr = 2;while (1) {int flg = 1;for (int i = 0; i < idx; ++i) {u64 a = _pr, b = (_mod - 1) / ds[i], r = 1;while (b) {if (b & 1) r = r * a % _mod;a = a * a % _mod;b >>= 1;}if (r == 1) {flg = 0;break;}}if (flg == 1) break;++_pr;}return _pr;};static constexpr uint32_t mod = mint::get_mod();static constexpr uint32_t pr = get_pr();static constexpr int level = __builtin_ctzll(mod - 1);mint dw[level], dy[level];void setwy(int k) {mint w[level], y[level];w[k - 1] = mint(pr).pow((mod - 1) / (1 << k));y[k - 1] = w[k - 1].inverse();for (int i = k - 2; i > 0; --i)w[i] = w[i + 1] * w[i + 1], y[i] = y[i + 1] * y[i + 1];dw[1] = w[1], dy[1] = y[1], dw[2] = w[2], dy[2] = y[2];for (int i = 3; i < k; ++i) {dw[i] = dw[i - 1] * y[i - 2] * w[i];dy[i] = dy[i - 1] * w[i - 2] * y[i];}}NTT() { setwy(level); }void fft4(vector<mint> &a, int k) {if ((int)a.size() <= 1) return;if (k == 1) {mint a1 = a[1];a[1] = a[0] - a[1];a[0] = a[0] + a1;return;}if (k & 1) {int v = 1 << (k - 1);for (int j = 0; j < v; ++j) {mint ajv = a[j + v];a[j + v] = a[j] - ajv;a[j] += ajv;}}int u = 1 << (2 + (k & 1));int v = 1 << (k - 2 - (k & 1));mint one = mint(1);mint imag = dw[1];while (v) {// jh = 0{int j0 = 0;int j1 = v;int j2 = j1 + v;int j3 = j2 + v;for (; j0 < v; ++j0, ++j1, ++j2, ++j3) {mint t0 = a[j0], t1 = a[j1], t2 = a[j2], t3 = a[j3];mint t0p2 = t0 + t2, t1p3 = t1 + t3;mint t0m2 = t0 - t2, t1m3 = (t1 - t3) * imag;a[j0] = t0p2 + t1p3, a[j1] = t0p2 - t1p3;a[j2] = t0m2 + t1m3, a[j3] = t0m2 - t1m3;}}// jh >= 1mint ww = one, xx = one * dw[2], wx = one;for (int jh = 4; jh < u;) {ww = xx * xx, wx = ww * xx;int j0 = jh * v;int je = j0 + v;int j2 = je + v;for (; j0 < je; ++j0, ++j2) {mint t0 = a[j0], t1 = a[j0 + v] * xx, t2 = a[j2] * ww,t3 = a[j2 + v] * wx;mint t0p2 = t0 + t2, t1p3 = t1 + t3;mint t0m2 = t0 - t2, t1m3 = (t1 - t3) * imag;a[j0] = t0p2 + t1p3, a[j0 + v] = t0p2 - t1p3;a[j2] = t0m2 + t1m3, a[j2 + v] = t0m2 - t1m3;}xx *= dw[__builtin_ctzll((jh += 4))];}u <<= 2;v >>= 2;}}void ifft4(vector<mint> &a, int k) {if ((int)a.size() <= 1) return;if (k == 1) {mint a1 = a[1];a[1] = a[0] - a[1];a[0] = a[0] + a1;return;}int u = 1 << (k - 2);int v = 1;mint one = mint(1);mint imag = dy[1];while (u) {// jh = 0{int j0 = 0;int j1 = v;int j2 = v + v;int j3 = j2 + v;for (; j0 < v; ++j0, ++j1, ++j2, ++j3) {mint t0 = a[j0], t1 = a[j1], t2 = a[j2], t3 = a[j3];mint t0p1 = t0 + t1, t2p3 = t2 + t3;mint t0m1 = t0 - t1, t2m3 = (t2 - t3) * imag;a[j0] = t0p1 + t2p3, a[j2] = t0p1 - t2p3;a[j1] = t0m1 + t2m3, a[j3] = t0m1 - t2m3;}}// jh >= 1mint ww = one, xx = one * dy[2], yy = one;u <<= 2;for (int jh = 4; jh < u;) {ww = xx * xx, yy = xx * imag;int j0 = jh * v;int je = j0 + v;int j2 = je + v;for (; j0 < je; ++j0, ++j2) {mint t0 = a[j0], t1 = a[j0 + v], t2 = a[j2], t3 = a[j2 + v];mint t0p1 = t0 + t1, t2p3 = t2 + t3;mint t0m1 = (t0 - t1) * xx, t2m3 = (t2 - t3) * yy;a[j0] = t0p1 + t2p3, a[j2] = (t0p1 - t2p3) * ww;a[j0 + v] = t0m1 + t2m3, a[j2 + v] = (t0m1 - t2m3) * ww;}xx *= dy[__builtin_ctzll(jh += 4)];}u >>= 4;v <<= 2;}if (k & 1) {u = 1 << (k - 1);for (int j = 0; j < u; ++j) {mint ajv = a[j] - a[j + u];a[j] += a[j + u];a[j + u] = ajv;}}}void ntt(vector<mint> &a) {if ((int)a.size() <= 1) return;fft4(a, __builtin_ctz(a.size()));}void intt(vector<mint> &a) {if ((int)a.size() <= 1) return;ifft4(a, __builtin_ctz(a.size()));mint iv = mint(a.size()).inverse();for (auto &x : a) x *= iv;}vector<mint> multiply(const vector<mint> &a, const vector<mint> &b) {int l = a.size() + b.size() - 1;if (min<int>(a.size(), b.size()) <= 40) {vector<mint> s(l);for (int i = 0; i < (int)a.size(); ++i)for (int j = 0; j < (int)b.size(); ++j) s[i + j] += a[i] * b[j];return s;}int k = 2, M = 4;while (M < l) M <<= 1, ++k;setwy(k);vector<mint> s(M), t(M);for (int i = 0; i < (int)a.size(); ++i) s[i] = a[i];for (int i = 0; i < (int)b.size(); ++i) t[i] = b[i];fft4(s, k);fft4(t, k);for (int i = 0; i < M; ++i) s[i] *= t[i];ifft4(s, k);s.resize(l);mint invm = mint(M).inverse();for (int i = 0; i < l; ++i) s[i] *= invm;return s;}void ntt_doubling(vector<mint> &a) {int M = (int)a.size();auto b = a;intt(b);mint r = 1, zeta = mint(pr).pow((mint::get_mod() - 1) / (M << 1));for (int i = 0; i < M; i++) b[i] *= r, r *= zeta;ntt(b);copy(begin(b), end(b), back_inserter(a));}};namespace ArbitraryNTT {using i64 = int64_t;using u128 = __uint128_t;constexpr int32_t m0 = 167772161;constexpr int32_t m1 = 469762049;constexpr int32_t m2 = 754974721;using mint0 = LazyMontgomeryModInt<m0>;using mint1 = LazyMontgomeryModInt<m1>;using mint2 = LazyMontgomeryModInt<m2>;constexpr int r01 = mint1(m0).inverse().get();constexpr int r02 = mint2(m0).inverse().get();constexpr int r12 = mint2(m1).inverse().get();constexpr int r02r12 = i64(r02) * r12 % m2;constexpr i64 w1 = m0;constexpr i64 w2 = i64(m0) * m1;template <typename T, typename submint>vector<submint> mul(const vector<T> &a, const vector<T> &b) {static NTT<submint> ntt;vector<submint> s(a.size()), t(b.size());for (int i = 0; i < (int)a.size(); ++i) s[i] = i64(a[i] % submint::get_mod());for (int i = 0; i < (int)b.size(); ++i) t[i] = i64(b[i] % submint::get_mod());return ntt.multiply(s, t);}template <typename T>vector<int> multiply(const vector<T> &s, const vector<T> &t, int mod) {auto d0 = mul<T, mint0>(s, t);auto d1 = mul<T, mint1>(s, t);auto d2 = mul<T, mint2>(s, t);int n = d0.size();vector<int> ret(n);const int W1 = w1 % mod;const int W2 = w2 % mod;for (int i = 0; i < n; i++) {int n1 = d1[i].get(), n2 = d2[i].get(), a = d0[i].get();int b = i64(n1 + m1 - a) * r01 % m1;int c = (i64(n2 + m2 - a) * r02r12 + i64(m2 - b) * r12) % m2;ret[i] = (i64(a) + i64(b) * W1 + i64(c) * W2) % mod;}return ret;}template <typename mint>vector<mint> multiply(const vector<mint> &a, const vector<mint> &b) {if (a.size() == 0 && b.size() == 0) return {};if (min<int>(a.size(), b.size()) < 128) {vector<mint> ret(a.size() + b.size() - 1);for (int i = 0; i < (int)a.size(); ++i)for (int j = 0; j < (int)b.size(); ++j) ret[i + j] += a[i] * b[j];return ret;}vector<int> s(a.size()), t(b.size());for (int i = 0; i < (int)a.size(); ++i) s[i] = a[i].get();for (int i = 0; i < (int)b.size(); ++i) t[i] = b[i].get();vector<int> u = multiply<int>(s, t, mint::get_mod());vector<mint> ret(u.size());for (int i = 0; i < (int)u.size(); ++i) ret[i] = mint(u[i]);return ret;}template <typename T>vector<u128> multiply_u128(const vector<T> &s, const vector<T> &t) {if (s.size() == 0 && t.size() == 0) return {};if (min<int>(s.size(), t.size()) < 128) {vector<u128> ret(s.size() + t.size() - 1);for (int i = 0; i < (int)s.size(); ++i)for (int j = 0; j < (int)t.size(); ++j) ret[i + j] += i64(s[i]) * t[j];return ret;}auto d0 = mul<T, mint0>(s, t);auto d1 = mul<T, mint1>(s, t);auto d2 = mul<T, mint2>(s, t);int n = d0.size();vector<u128> ret(n);for (int i = 0; i < n; i++) {i64 n1 = d1[i].get(), n2 = d2[i].get();i64 a = d0[i].get();i64 b = (n1 + m1 - a) * r01 % m1;i64 c = ((n2 + m2 - a) * r02r12 + (m2 - b) * r12) % m2;ret[i] = a + b * w1 + u128(c) * w2;}return ret;}} // namespace ArbitraryNTTusing namespace Nyaan;void q() {ini(N, M);ins(S1, S2);vl S(N + M - 1);{vl A(N), B(M), C(N), D(M);rep(i, N) {A[i] = S1[i] == '?' ? 0 : S1[i];C[i] = S1[i] == '?' ? 0 : 1;}rep(i, M) {B[i] = S2[i];D[i] = 1;}// i 文字目以降が一致// F(i) = sum_{0<=j<M} C_{i+j} D_j (A_{i+j} - B_j)^2 = 0vl A1(N), A2(N), A3(N);vl B1(M), B2(M), B3(M);rep(i, N) {A1[i] = C[i] * A[i] * A[i];A2[i] = C[i] * A[i] * (-2);A3[i] = C[i];}rep(i, M) {B1[i] = D[i];B2[i] = D[i] * B[i];B3[i] = D[i] * B[i] * B[i];}reverse(all(B1)), reverse(all(B2)), reverse(all(B3));vl _a1(N), _a2(N), _a3(N), _b1(M), _b2(M), _b3(M);for (int mod : {1000000007, 1000000009}) {rep(i, N) {_a1[i] = A1[i] < 0 ? mod + A1[i] : A1[i];_a2[i] = A2[i] < 0 ? mod + A2[i] : A2[i];_a3[i] = A3[i] < 0 ? mod + A3[i] : A3[i];}rep(i, M) {_b1[i] = B1[i] < 0 ? mod + B1[i] : B1[i];_b2[i] = B2[i] < 0 ? mod + B2[i] : B2[i];_b3[i] = B3[i] < 0 ? mod + B3[i] : B3[i];}auto AB1 = ArbitraryNTT::multiply(_a1, _b1, mod);auto AB2 = ArbitraryNTT::multiply(_a2, _b2, mod);auto AB3 = ArbitraryNTT::multiply(_a3, _b3, mod);rep(i, N + M - 1) {int x = (ll(AB1[i]) + AB2[i] + AB3[i]) % mod;if (x != 0) S[i] = 1;}}trc(S);}string U;each(c, S1) U.push_back(c == '?' ? 'a' : c);each(c, S2) U.push_back(c);StringSearch ss{U};auto comp = [&](vp a, vp b) {reverse(all(a)), reverse(all(b));while (sz(a)) {assert(sz(b));auto p = a.back();auto q = b.back();int m = min(p.se - p.fi, q.se - q.fi);a.back().fi += m;b.back().fi += m;if (a.back().fi == a.back().se) a.pop_back();if (b.back().fi == b.back().se) b.pop_back();int c = ss.strcmp(p.fi, p.fi + m, q.fi, q.fi + m);if (c != 0) return c < 0;}return false;};pair<int, vp> ans{-1, {}};rep(i, N - M + 1) {if (S[i + M - 1] == 0) {vp v;v.emplace_back(0, i);v.emplace_back(N, N + M);v.emplace_back(i + M, N);if (ans.fi == -1 or comp(v, ans.se)) {ans = {i, v};}}}if (ans.fi == -1) {out(-1);} else {int i = ans.fi;rep(j, M) S1[j + i] = S2[j];rep(j, N) if (S1[j] == '?') S1[j] = 'a';out(S1);}}void Nyaan::solve() {int t = 1;in(t);while (t--) q();}