結果
| 問題 |
No.2231 Surprising Flash!
|
| コンテスト | |
| ユーザー |
 hitonanode
|
| 提出日時 | 2023-02-24 22:48:09 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 36,181 bytes |
| コンパイル時間 | 5,298 ms |
| コンパイル使用メモリ | 256,544 KB |
| 実行使用メモリ | 105,084 KB |
| 最終ジャッジ日時 | 2024-09-13 08:02:55 |
| 合計ジャッジ時間 | 21,964 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 37 WA * 7 |
ソースコード
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <deque>
#include <forward_list>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using lint = long long;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
struct fast_ios { fast_ios(){ cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(20); }; } fast_ios_;
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
template <typename T, typename V>
void ndarray(vector<T>& vec, const V& val, int len) { vec.assign(len, val); }
template <typename T, typename V, typename... Args> void ndarray(vector<T>& vec, const V& val, int len, Args... args) { vec.resize(len), for_each(begin(vec), end(vec), [&](T& v) { ndarray(v, val, args...); }); }
template <typename T> bool chmax(T &m, const T q) { return m < q ? (m = q, true) : false; }
template <typename T> bool chmin(T &m, const T q) { return m > q ? (m = q, true) : false; }
const std::vector<std::pair<int, int>> grid_dxs{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int floor_lg(long long x) { return x <= 0 ? -1 : 63 - __builtin_clzll(x); }
template <class T1, class T2> T1 floor_div(T1 num, T2 den) { return (num > 0 ? num / den : -((-num + den - 1) / den)); }
template <class T1, class T2> std::pair<T1, T2> operator+(const std::pair<T1, T2> &l, const std::pair<T1, T2> &r) { return std::make_pair(l.first + r.first, l.second + r.second); }
template <class T1, class T2> std::pair<T1, T2> operator-(const std::pair<T1, T2> &l, const std::pair<T1, T2> &r) { return std::make_pair(l.first - r.first, l.second - r.second); }
template <class T> std::vector<T> sort_unique(std::vector<T> vec) { sort(vec.begin(), vec.end()), vec.erase(unique(vec.begin(), vec.end()), vec.end()); return vec; }
template <class T> int arglb(const std::vector<T> &v, const T &x) { return std::distance(v.begin(), std::lower_bound(v.begin(), v.end(), x)); }
template <class T> int argub(const std::vector<T> &v, const T &x) { return std::distance(v.begin(), std::upper_bound(v.begin(), v.end(), x)); }
template <class IStream, class T> IStream &operator>>(IStream &is, std::vector<T> &vec) { for (auto &v : vec) is >> v; return is; }
template <class OStream, class T> OStream &operator<<(OStream &os, const std::vector<T> &vec);
template <class OStream, class T, size_t sz> OStream &operator<<(OStream &os, const std::array<T, sz> &arr);
template <class OStream, class T, class TH> OStream &operator<<(OStream &os, const std::unordered_set<T, TH> &vec);
template <class OStream, class T, class U> OStream &operator<<(OStream &os, const pair<T, U> &pa);
template <class OStream, class T> OStream &operator<<(OStream &os, const std::deque<T> &vec);
template <class OStream, class T> OStream &operator<<(OStream &os, const std::set<T> &vec);
template <class OStream, class T> OStream &operator<<(OStream &os, const std::multiset<T> &vec);
template <class OStream, class T> OStream &operator<<(OStream &os, const std::unordered_multiset<T> &vec);
template <class OStream, class T, class U> OStream &operator<<(OStream &os, const std::pair<T, U> &pa);
template <class OStream, class TK, class TV> OStream &operator<<(OStream &os, const std::map<TK, TV> &mp);
template <class OStream, class TK, class TV, class TH> OStream &operator<<(OStream &os, const std::unordered_map<TK, TV, TH> &mp);
template <class OStream, class... T> OStream &operator<<(OStream &os, const std::tuple<T...> &tpl);
template <class OStream, class T> OStream &operator<<(OStream &os, const std::vector<T> &vec) { os << '['; for (auto v : vec) os << v << ','; os << ']'; return os; }
template <class OStream, class T, size_t sz> OStream &operator<<(OStream &os, const std::array<T, sz> &arr) { os << '['; for (auto v : arr) os << v << ','; os << ']'; return os; }
template <class... T> std::istream &operator>>(std::istream &is, std::tuple<T...> &tpl) { std::apply([&is](auto &&... args) { ((is >> args), ...);}, tpl); return is; }
template <class OStream, class... T> OStream &operator<<(OStream &os, const std::tuple<T...> &tpl) { os << '('; std::apply([&os](auto &&... args) { ((os << args << ','), ...);}, tpl); return os << ')'; }
template <class OStream, class T, class TH> OStream &operator<<(OStream &os, const std::unordered_set<T, TH> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; }
template <class OStream, class T> OStream &operator<<(OStream &os, const std::deque<T> &vec) { os << "deq["; for (auto v : vec) os << v << ','; os << ']'; return os; }
template <class OStream, class T> OStream &operator<<(OStream &os, const std::set<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; }
template <class OStream, class T> OStream &operator<<(OStream &os, const std::multiset<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; }
template <class OStream, class T> OStream &operator<<(OStream &os, const std::unordered_multiset<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; }
template <class OStream, class T, class U> OStream &operator<<(OStream &os, const std::pair<T, U> &pa) { return os << '(' << pa.first << ',' << pa.second << ')'; }
template <class OStream, class TK, class TV> OStream &operator<<(OStream &os, const std::map<TK, TV> &mp) { os << '{'; for (auto v : mp) os << v.first << "=>" << v.second << ','; os << '}'; return os; }
template <class OStream, class TK, class TV, class TH> OStream &operator<<(OStream &os, const std::unordered_map<TK, TV, TH> &mp) { os << '{'; for (auto v : mp) os << v.first << "=>" << v.second << ','; os << '}'; return os; }
#ifdef HITONANODE_LOCAL
const string COLOR_RESET = "\033[0m", BRIGHT_GREEN = "\033[1;32m", BRIGHT_RED = "\033[1;31m", BRIGHT_CYAN = "\033[1;36m", NORMAL_CROSSED = "\033[0;9;37m", RED_BACKGROUND = "\033[1;41m", NORMAL_FAINT = "\033[0;2m";
#define dbg(x) std::cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) << NORMAL_FAINT << " (L" << __LINE__ << ") " << __FILE__ << COLOR_RESET << std::endl
#define dbgif(cond, x) ((cond) ? std::cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) << NORMAL_FAINT << " (L" << __LINE__ << ") " << __FILE__ << COLOR_RESET << std::endl : std::cerr)
#else
#define dbg(x) ((void)0)
#define dbgif(cond, x) ((void)0)
#endif
template <int md> struct ModInt {
#if __cplusplus >= 201402L
#define MDCONST constexpr
#else
#define MDCONST
#endif
using lint = long long;
MDCONST static int mod() { return md; }
static int get_primitive_root() {
static int primitive_root = 0;
if (!primitive_root) {
primitive_root = [&]() {
std::set<int> fac;
int v = md - 1;
for (lint i = 2; i * i <= v; i++)
while (v % i == 0) fac.insert(i), v /= i;
if (v > 1) fac.insert(v);
for (int g = 1; g < md; g++) {
bool ok = true;
for (auto i : fac)
if (ModInt(g).pow((md - 1) / i) == 1) {
ok = false;
break;
}
if (ok) return g;
}
return -1;
}();
}
return primitive_root;
}
int val_;
int val() const noexcept { return val_; }
MDCONST ModInt() : val_(0) {}
MDCONST ModInt &_setval(lint v) { return val_ = (v >= md ? v - md : v), *this; }
MDCONST ModInt(lint v) { _setval(v % md + md); }
MDCONST explicit operator bool() const { return val_ != 0; }
MDCONST ModInt operator+(const ModInt &x) const {
return ModInt()._setval((lint)val_ + x.val_);
}
MDCONST ModInt operator-(const ModInt &x) const {
return ModInt()._setval((lint)val_ - x.val_ + md);
}
MDCONST ModInt operator*(const ModInt &x) const {
return ModInt()._setval((lint)val_ * x.val_ % md);
}
MDCONST ModInt operator/(const ModInt &x) const {
return ModInt()._setval((lint)val_ * x.inv().val() % md);
}
MDCONST ModInt operator-() const { return ModInt()._setval(md - val_); }
MDCONST ModInt &operator+=(const ModInt &x) { return *this = *this + x; }
MDCONST ModInt &operator-=(const ModInt &x) { return *this = *this - x; }
MDCONST ModInt &operator*=(const ModInt &x) { return *this = *this * x; }
MDCONST ModInt &operator/=(const ModInt &x) { return *this = *this / x; }
friend MDCONST ModInt operator+(lint a, const ModInt &x) {
return ModInt()._setval(a % md + x.val_);
}
friend MDCONST ModInt operator-(lint a, const ModInt &x) {
return ModInt()._setval(a % md - x.val_ + md);
}
friend MDCONST ModInt operator*(lint a, const ModInt &x) {
return ModInt()._setval(a % md * x.val_ % md);
}
friend MDCONST ModInt operator/(lint a, const ModInt &x) {
return ModInt()._setval(a % md * x.inv().val() % md);
}
MDCONST bool operator==(const ModInt &x) const { return val_ == x.val_; }
MDCONST bool operator!=(const ModInt &x) const { return val_ != x.val_; }
MDCONST bool operator<(const ModInt &x) const {
return val_ < x.val_;
} // To use std::map<ModInt, T>
friend std::istream &operator>>(std::istream &is, ModInt &x) {
lint t;
return is >> t, x = ModInt(t), is;
}
MDCONST friend std::ostream &operator<<(std::ostream &os, const ModInt &x) {
return os << x.val_;
}
MDCONST ModInt pow(lint n) const {
ModInt ans = 1, tmp = *this;
while (n) {
if (n & 1) ans *= tmp;
tmp *= tmp, n >>= 1;
}
return ans;
}
static std::vector<ModInt> facs, facinvs, invs;
MDCONST static void _precalculation(int N) {
int l0 = facs.size();
if (N > md) N = md;
if (N <= l0) return;
facs.resize(N), facinvs.resize(N), invs.resize(N);
for (int i = l0; i < N; i++) facs[i] = facs[i - 1] * i;
facinvs[N - 1] = facs.back().pow(md - 2);
for (int i = N - 2; i >= l0; i--) facinvs[i] = facinvs[i + 1] * (i + 1);
for (int i = N - 1; i >= l0; i--) invs[i] = facinvs[i] * facs[i - 1];
}
MDCONST ModInt inv() const {
if (this->val_ < std::min(md >> 1, 1 << 21)) {
if (facs.empty()) facs = {1}, facinvs = {1}, invs = {0};
while (this->val_ >= int(facs.size())) _precalculation(facs.size() * 2);
return invs[this->val_];
} else {
return this->pow(md - 2);
}
}
MDCONST ModInt fac() const {
while (this->val_ >= int(facs.size())) _precalculation(facs.size() * 2);
return facs[this->val_];
}
MDCONST ModInt facinv() const {
while (this->val_ >= int(facs.size())) _precalculation(facs.size() * 2);
return facinvs[this->val_];
}
MDCONST ModInt doublefac() const {
lint k = (this->val_ + 1) / 2;
return (this->val_ & 1) ? ModInt(k * 2).fac() / (ModInt(2).pow(k) * ModInt(k).fac())
: ModInt(k).fac() * ModInt(2).pow(k);
}
MDCONST ModInt nCr(const ModInt &r) const {
return (this->val_ < r.val_) ? 0 : this->fac() * (*this - r).facinv() * r.facinv();
}
MDCONST ModInt nPr(const ModInt &r) const {
return (this->val_ < r.val_) ? 0 : this->fac() * (*this - r).facinv();
}
ModInt sqrt() const {
if (val_ == 0) return 0;
if (md == 2) return val_;
if (pow((md - 1) / 2) != 1) return 0;
ModInt b = 1;
while (b.pow((md - 1) / 2) == 1) b += 1;
int e = 0, m = md - 1;
while (m % 2 == 0) m >>= 1, e++;
ModInt x = pow((m - 1) / 2), y = (*this) * x * x;
x *= (*this);
ModInt z = b.pow(m);
while (y != 1) {
int j = 0;
ModInt t = y;
while (t != 1) j++, t *= t;
z = z.pow(1LL << (e - j - 1));
x *= z, z *= z, y *= z;
e = j;
}
return ModInt(std::min(x.val_, md - x.val_));
}
};
template <int md> std::vector<ModInt<md>> ModInt<md>::facs = {1};
template <int md> std::vector<ModInt<md>> ModInt<md>::facinvs = {1};
template <int md> std::vector<ModInt<md>> ModInt<md>::invs = {0};
using mint = ModInt<998244353>;
// Integer convolution for arbitrary mod
// with NTT (and Garner's algorithm) for ModInt / ModIntRuntime class.
// We skip Garner's algorithm if `skip_garner` is true or mod is in `nttprimes`.
// input: a (size: n), b (size: m)
// return: vector (size: n + m - 1)
template <typename MODINT>
std::vector<MODINT> nttconv(std::vector<MODINT> a, std::vector<MODINT> b, bool skip_garner);
constexpr int nttprimes[3] = {998244353, 167772161, 469762049};
// Integer FFT (Fast Fourier Transform) for ModInt class
// (Also known as Number Theoretic Transform, NTT)
// is_inverse: inverse transform
// ** Input size must be 2^n **
template <typename MODINT> void ntt(std::vector<MODINT> &a, bool is_inverse = false) {
int n = a.size();
if (n == 1) return;
static const int mod = MODINT::mod();
static const MODINT root = MODINT::get_primitive_root();
assert(__builtin_popcount(n) == 1 and (mod - 1) % n == 0);
static std::vector<MODINT> w{1}, iw{1};
for (int m = w.size(); m < n / 2; m *= 2) {
MODINT dw = root.pow((mod - 1) / (4 * m)), dwinv = 1 / dw;
w.resize(m * 2), iw.resize(m * 2);
for (int i = 0; i < m; i++) w[m + i] = w[i] * dw, iw[m + i] = iw[i] * dwinv;
}
if (!is_inverse) {
for (int m = n; m >>= 1;) {
for (int s = 0, k = 0; s < n; s += 2 * m, k++) {
for (int i = s; i < s + m; i++) {
MODINT x = a[i], y = a[i + m] * w[k];
a[i] = x + y, a[i + m] = x - y;
}
}
}
} else {
for (int m = 1; m < n; m *= 2) {
for (int s = 0, k = 0; s < n; s += 2 * m, k++) {
for (int i = s; i < s + m; i++) {
MODINT x = a[i], y = a[i + m];
a[i] = x + y, a[i + m] = (x - y) * iw[k];
}
}
}
int n_inv = MODINT(n).inv().val();
for (auto &v : a) v *= n_inv;
}
}
template <int MOD>
std::vector<ModInt<MOD>> nttconv_(const std::vector<int> &a, const std::vector<int> &b) {
int sz = a.size();
assert(a.size() == b.size() and __builtin_popcount(sz) == 1);
std::vector<ModInt<MOD>> ap(sz), bp(sz);
for (int i = 0; i < sz; i++) ap[i] = a[i], bp[i] = b[i];
ntt(ap, false);
if (a == b)
bp = ap;
else
ntt(bp, false);
for (int i = 0; i < sz; i++) ap[i] *= bp[i];
ntt(ap, true);
return ap;
}
long long garner_ntt_(int r0, int r1, int r2, int mod) {
using mint2 = ModInt<nttprimes[2]>;
static const long long m01 = 1LL * nttprimes[0] * nttprimes[1];
static const long long m0_inv_m1 = ModInt<nttprimes[1]>(nttprimes[0]).inv().val();
static const long long m01_inv_m2 = mint2(m01).inv().val();
int v1 = (m0_inv_m1 * (r1 + nttprimes[1] - r0)) % nttprimes[1];
auto v2 = (mint2(r2) - r0 - mint2(nttprimes[0]) * v1) * m01_inv_m2;
return (r0 + 1LL * nttprimes[0] * v1 + m01 % mod * v2.val()) % mod;
}
template <typename MODINT>
std::vector<MODINT> nttconv(std::vector<MODINT> a, std::vector<MODINT> b, bool skip_garner) {
if (a.empty() or b.empty()) return {};
int sz = 1, n = a.size(), m = b.size();
while (sz < n + m) sz <<= 1;
if (sz <= 16) {
std::vector<MODINT> ret(n + m - 1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) ret[i + j] += a[i] * b[j];
}
return ret;
}
int mod = MODINT::mod();
if (skip_garner or
std::find(std::begin(nttprimes), std::end(nttprimes), mod) != std::end(nttprimes)) {
a.resize(sz), b.resize(sz);
if (a == b) {
ntt(a, false);
b = a;
} else {
ntt(a, false), ntt(b, false);
}
for (int i = 0; i < sz; i++) a[i] *= b[i];
ntt(a, true);
a.resize(n + m - 1);
} else {
std::vector<int> ai(sz), bi(sz);
for (int i = 0; i < n; i++) ai[i] = a[i].val();
for (int i = 0; i < m; i++) bi[i] = b[i].val();
auto ntt0 = nttconv_<nttprimes[0]>(ai, bi);
auto ntt1 = nttconv_<nttprimes[1]>(ai, bi);
auto ntt2 = nttconv_<nttprimes[2]>(ai, bi);
a.resize(n + m - 1);
for (int i = 0; i < n + m - 1; i++)
a[i] = garner_ntt_(ntt0[i].val(), ntt1[i].val(), ntt2[i].val(), mod);
}
return a;
}
template <typename MODINT>
std::vector<MODINT> nttconv(const std::vector<MODINT> &a, const std::vector<MODINT> &b) {
return nttconv<MODINT>(a, b, false);
}
// F_p, p = 2^61 - 1
// https://qiita.com/keymoon/items/11fac5627672a6d6a9f6
class ModIntMersenne61 {
static const long long md = (1LL << 61) - 1;
long long _v;
inline unsigned hi() const noexcept { return _v >> 31; }
inline unsigned lo() const noexcept { return _v & ((1LL << 31) - 1); }
public:
static long long mod() { return md; }
ModIntMersenne61() : _v(0) {}
// 0 <= x < md * 2
explicit ModIntMersenne61(long long x) : _v(x >= md ? x - md : x) {}
long long val() const noexcept { return _v; }
ModIntMersenne61 operator+(const ModIntMersenne61 &x) const {
return ModIntMersenne61(_v + x._v);
}
ModIntMersenne61 operator-(const ModIntMersenne61 &x) const {
return ModIntMersenne61(_v + md - x._v);
}
ModIntMersenne61 operator*(const ModIntMersenne61 &x) const {
using ull = unsigned long long;
ull uu = (ull)hi() * x.hi() * 2;
ull ll = (ull)lo() * x.lo();
ull lu = (ull)hi() * x.lo() + (ull)lo() * x.hi();
ull sum = uu + ll + ((lu & ((1ULL << 30) - 1)) << 31) + (lu >> 30);
ull reduced = (sum >> 61) + (sum & ull(md));
return ModIntMersenne61(reduced);
}
ModIntMersenne61 pow(long long n) const {
assert(n >= 0);
ModIntMersenne61 ans(1), tmp = *this;
while (n) {
if (n & 1) ans *= tmp;
tmp *= tmp, n >>= 1;
}
return ans;
}
ModIntMersenne61 inv() const { return pow(md - 2); }
ModIntMersenne61 operator/(const ModIntMersenne61 &x) const { return *this * x.inv(); }
ModIntMersenne61 operator-() const { return ModIntMersenne61(md - _v); }
ModIntMersenne61 &operator+=(const ModIntMersenne61 &x) { return *this = *this + x; }
ModIntMersenne61 &operator-=(const ModIntMersenne61 &x) { return *this = *this - x; }
ModIntMersenne61 &operator*=(const ModIntMersenne61 &x) { return *this = *this * x; }
ModIntMersenne61 &operator/=(const ModIntMersenne61 &x) { return *this = *this / x; }
ModIntMersenne61 operator+(unsigned x) const { return ModIntMersenne61(this->_v + x); }
bool operator==(const ModIntMersenne61 &x) const { return _v == x._v; }
bool operator!=(const ModIntMersenne61 &x) const { return _v != x._v; }
bool operator<(const ModIntMersenne61 &x) const { return _v < x._v; } // To use std::map
template <class OStream> friend OStream &operator<<(OStream &os, const ModIntMersenne61 &x) {
return os << x._v;
}
static ModIntMersenne61 randgen(bool force_update = false) {
static ModIntMersenne61 b(0);
if (b == ModIntMersenne61(0) or force_update) {
std::mt19937 mt(std::chrono::steady_clock::now().time_since_epoch().count());
std::uniform_int_distribution<long long> d(1, ModIntMersenne61::mod());
b = ModIntMersenne61(d(mt));
}
return b;
}
};
template <class T1, class T2> struct PairHash : public std::pair<T1, T2> {
using PH = PairHash<T1, T2>;
explicit PairHash(T1 x, T2 y) : std::pair<T1, T2>(x, y) {}
explicit PairHash(int x) : std::pair<T1, T2>(x, x) {}
PairHash() : PairHash(0) {}
PH operator+(const PH &x) const { return PH(this->first + x.first, this->second + x.second); }
PH operator-(const PH &x) const { return PH(this->first - x.first, this->second - x.second); }
PH operator*(const PH &x) const { return PH(this->first * x.first, this->second * x.second); }
PH operator+(int x) const { return PH(this->first + x, this->second + x); }
static PH randgen(bool force_update = false) {
static PH b(0);
if (b == PH(0) or force_update) {
std::mt19937 mt(std::chrono::steady_clock::now().time_since_epoch().count());
std::uniform_int_distribution<int> d(1 << 30);
b = PH(T1(d(mt)), T2(d(mt)));
}
return b;
}
};
template <class T1, class T2, class T3> struct TupleHash3 : public std::tuple<T1, T2, T3> {
using TH = TupleHash3<T1, T2, T3>;
explicit TupleHash3(T1 x, T2 y, T3 z) : std::tuple<T1, T2, T3>(x, y, z) {}
explicit TupleHash3(int x) : std::tuple<T1, T2, T3>(x, x, x) {}
TupleHash3() : TupleHash3(0) {}
inline const T1 &v1() const noexcept { return std::get<0>(*this); }
inline const T2 &v2() const noexcept { return std::get<1>(*this); }
inline const T3 &v3() const noexcept { return std::get<2>(*this); }
TH operator+(const TH &x) const { return TH(v1() + x.v1(), v2() + x.v2(), v3() + x.v3()); }
TH operator-(const TH &x) const { return TH(v1() - x.v1(), v2() - x.v2(), v3() - x.v3()); }
TH operator*(const TH &x) const { return TH(v1() * x.v1(), v2() * x.v2(), v3() * x.v3()); }
TH operator+(int x) const { return TH(v1() + x, v2() + x, v3() + x); }
static TH randgen(bool force_update = false) {
static TH b(0);
if (b == TH(0) or force_update) {
std::mt19937 mt(std::chrono::steady_clock::now().time_since_epoch().count());
std::uniform_int_distribution<int> d(1 << 30);
b = TH(T1(d(mt)), T2(d(mt)), T3(d(mt)));
}
return b;
}
};
// Rolling Hash (Rabin-Karp), 1dim
template <typename V> struct rolling_hash {
int N;
const V B;
std::vector<V> hash; // hash[i] = s[0] * B^(i - 1) + ... + s[i - 1]
static std::vector<V> power; // power[i] = B^i
void _extend_powvec() {
if (power.size() > 1 and power.at(1) != B) power = {V(1)};
while (static_cast<int>(power.size()) <= N) {
auto tmp = power.back() * B;
power.push_back(tmp);
}
}
template <typename Int>
rolling_hash(const std::vector<Int> &s, V b = V::randgen()) : N(s.size()), B(b), hash(N + 1) {
for (int i = 0; i < N; i++) hash[i + 1] = hash[i] * B + s[i];
_extend_powvec();
}
rolling_hash(const std::string &s = "", V b = V::randgen()) : N(s.size()), B(b), hash(N + 1) {
for (int i = 0; i < N; i++) hash[i + 1] = hash[i] * B + s[i];
_extend_powvec();
}
void addchar(const char &c) {
V hnew = hash[N] * B + c;
N++, hash.emplace_back(hnew);
_extend_powvec();
}
V get(int l, int r) const { // s[l] * B^(r - l - 1) + ... + s[r - 1]
return hash[r] - hash[l] * power[r - l];
}
int lcplen(int l1, int l2) const { return longest_common_prefix(*this, l1, *this, l2); }
};
template <typename V> std::vector<V> rolling_hash<V>::power{V(1)};
// Longest common prerfix between s1[l1, N1) and s2[l2, N2)
template <typename T>
int longest_common_prefix(const rolling_hash<T> &rh1, int l1, const rolling_hash<T> &rh2, int l2) {
int lo = 0, hi = std::min(rh1.N + 1 - l1, rh2.N + 1 - l2);
while (hi - lo > 1) {
const int c = (lo + hi) / 2;
auto h1 = rh1.get(l1, l1 + c), h2 = rh2.get(l2, l2 + c);
(h1 == h2 ? lo : hi) = c;
}
return lo;
}
// Longest common suffix between s1[0, r1) and s2[0, r2)
template <typename T>
int longest_common_suffix(const rolling_hash<T> &rh1, int r1, const rolling_hash<T> &rh2, int r2) {
int lo = 0, hi = std::min(r1, r2) + 1;
while (hi - lo > 1) {
const int c = (lo + hi) / 2;
auto h1 = rh1.get(r1 - c, r1), h2 = rh2.get(r2 - c, r2);
(h1 == h2 ? lo : hi) = c;
}
return lo;
}
// Z algorithm (length of longest common prefix for s[0:N] & s[i:N] for each i)
// Input: std::vector<T> / std::string of length N
// Output: std::vector<int> of size N
// Complexity: O(N)
// Sample:
// - `teletelepathy` -> [13, 0, 0, 0, 4, 0, 0, 0, 0, 0, 1, 0, 0]
// Reference: <http://snuke.hatenablog.com/entry/2014/12/03/214243>
template <typename T> std::vector<int> z_algorithm(const std::vector<T> &s) {
const int N = s.size();
if (N == 0) return {};
std::vector<int> ans(N);
ans[0] = N;
int i = 1, j = 0;
while (i < N) {
while (i + j < N and s[j] == s[i + j]) ++j;
ans[i] = j;
if (!j) {
++i;
continue;
}
int k = 1;
while (i + k < N and k + ans[k] < j) ans[i + k] = ans[k], ++k;
i += k;
j -= k;
}
return ans;
}
std::vector<int> z_algorithm(const std::string &s) {
const int N = int(s.size());
std::vector<int> v(N);
for (int i = 0; i < N; i++) v[i] = s[i];
return z_algorithm(v);
}
#include <algorithm>
#include <cassert>
#include <numeric>
#include <string>
#include <vector>
// Suffix array algorithms from AtCoder Library
// Document: <https://atcoder.github.io/ac-library/master/document_ja/string.html>
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 Construction
template <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 internal
std::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
// Applications
template <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);
}
uint32_t rand_int() // XorShift random integer generator
{
static uint32_t x = 123456789, y = 362436069, z = 521288629, w = 88675123;
uint32_t t = x ^ (x << 11);
x = y;
y = z;
z = w;
return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}
double rand_double() { return (double)rand_int() / UINT32_MAX; }
#include <atcoder/segtree>
int op(int l, int r) { return std::min(l, r); }
int e() { return 0; }
string solve(const string &S1, const string &S2) {
const int N = S1.size(), M = S2.size();
string S1a = S1;
for (auto &c : S1a) {
if (c == '?') c = 'a';
}
rolling_hash<ModIntMersenne61> rh1a(S1a);
rolling_hash<ModIntMersenne61> rh2(S2);
const auto z_algo = z_algorithm(S2 + "_" + S1a);
const auto sa = suffix_array(S2 + "_" + S1a);
dbg(sa);
vector<int> sainv(sa.size());
REP(i, sa.size()) sainv.at(sa.at(i)) = i;
const auto lcp = lcp_array(S2 + "_" + S1a, sa);
atcoder::segtree<int, op, e> lcptree(lcp);
REP(_, 1000) rand_int();
vector<mint> hash(26);
for (auto &x : hash) x = rand_int();
vector<mint> f, g;
for (auto c : S1) {
if (c == '?') {
f.push_back(0);
} else {
f.push_back(hash.at(c - 'a'));
}
}
for (auto c : S2) g.push_back(hash.at(c - 'a'));
vector<mint> f2 = f;
for (auto &x : f2) x *= x;
vector<mint> f3 = f2;
REP(i, f3.size()) f3.at(i) *= f.at(i);
vector<mint> g2 = g;
for (auto &x : g2) x *= x;
vector<mint> g0(g.size(), 1);
reverse(ALL(g0));
reverse(ALL(g));
reverse(ALL(g2));
auto conv = nttconv(g0, f3), c2 = nttconv(g, f2), c3 = nttconv(g2, f);
REP(i, conv.size()) conv.at(i) += c3.at(i) - c2.at(i) * 2;
// dbg(conv);
vector<int> heads;
FOR(i, M - 1, N) if (conv.at(i) == 0) heads.push_back(i - (M - 1));
dbg(heads);
if (heads.empty()) return "-1";
// -1: same
auto solve = [&](int l, int r) -> int {
assert(l < r);
if (r - l < M) {
if (int z = z_algo.at(M + 1 + l); z < r - l) {
auto rhs = S1a.at(l + z), lhs = S2.at(z);
return lhs < rhs;
}
if (int z = z_algo.at(r - l); z < M - (r - l)) {
auto lhs = S2.at(r - l + z), rhs = S2.at(r - l);
return lhs < rhs;
}
int matchlen = longest_common_prefix(rh1a, l + M, rh2, M - (r - l));
if (matchlen >= r - l) return -1;
auto lhs = S1a.at(l + M + matchlen), rhs = S2.at(M - (r - l) + matchlen);
return lhs < rhs;
} else {
int lcur = sainv.at(0), rcur = sainv.at(M + 1 + l);
int match = lcptree.prod(min(lcur, rcur), max(lcur, rcur));
if (match < M) {
auto lhs = S2.at(match);
auto rhs = S1a.at(l + match);
return lhs < rhs;
}
lcur = sainv.at(M + 1 + r), rcur = sainv.at(0);
match = lcptree.prod(min(lcur, rcur), max(lcur, rcur));
if (match < M) {
auto lhs = S2.at(r + match);
auto rhs = S1a.at(match);
return lhs < rhs;
}
return -1;
}
};
auto comp = [&](int l, int r) -> bool {
if (l == r) return false;
if (l < r) {
auto ret = solve(l, r);
if (ret < 0) return false;
return ret;
} else {
auto ret = solve(r, l);
if (ret < 0) return false;
return ret ^ 1;
}
};
std::sort(heads.begin(), heads.end(), comp);
string ret = S1a.substr(0, heads.front()) + S2 + S1a.substr(heads.front() + S2.size());
return ret;
}
int main() {
int T;
cin >> T;
while (T--) {
int N, M;
string S1, S2;
cin >> N >> M >> S1 >> S2;
cout << solve(S1, S2) << '\n';
}
}