結果
| 問題 | No.2226 Hello, Forgotten World! |
| ユーザー |
 maksim
|
| 提出日時 | 2023-02-24 23:13:57 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 55 ms / 2,000 ms |
| コード長 | 21,081 bytes |
| コンパイル時間 | 11,323 ms |
| コンパイル使用メモリ | 508,564 KB |
| 実行使用メモリ | 27,724 KB |
| 最終ジャッジ日時 | 2024-09-13 06:04:49 |
| 合計ジャッジ時間 | 11,155 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 9 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int sp[maxn][20];
template <typename T>
vector<int> suffix_array(int n, const T &s, int char_bound) {
vector<int> a(n);
if (n == 0) {
return a;
}
if (char_bound != -1) {
vector<int> aux(char_bound, 0);
for (int i = 0; i < n; i++) {
aux[s[i]]++;
}
int sum = 0;
for (int i = 0; i < char_bound; i++) {
int add = aux[i];
aux[i] = sum;
sum += add;
}
for (int i = 0; i < n; i++) {
a[aux[s[i]]++] = i;
}
} else {
iota(a.begin(), a.end(), 0);
sort(a.begin(), a.end(), [&s](int i, int j) { return s[i] < s[j]; });
}
vector<int> sorted_by_second(n);
vector<int> ptr_group(n);
vector<int> new_group(n);
vector<int> group(n);
group[a[0]] = 0;
for (int i = 1; i < n; i++) {
group[a[i]] = group[a[i - 1]] + (!(s[a[i]] == s[a[i - 1]]));
}
int cnt = group[a[n - 1]] + 1;
int step = 1;
while (cnt < n) {
int at = 0;
for (int i = n - step; i < n; i++) {
sorted_by_second[at++] = i;
}
for (int i = 0; i < n; i++) {
if (a[i] - step >= 0) {
sorted_by_second[at++] = a[i] - step;
}
}
for (int i = n - 1; i >= 0; i--) {
ptr_group[group[a[i]]] = i;
}
for (int i = 0; i < n; i++) {
int x = sorted_by_second[i];
a[ptr_group[group[x]]++] = x;
}
new_group[a[0]] = 0;
for (int i = 1; i < n; i++) {
if (group[a[i]] != group[a[i - 1]]) {
new_group[a[i]] = new_group[a[i - 1]] + 1;
} else {
int pre = (a[i - 1] + step >= n ? -1 : group[a[i - 1] + step]);
int cur = (a[i] + step >= n ? -1 : group[a[i] + step]);
new_group[a[i]] = new_group[a[i - 1]] + (pre != cur);
}
}
swap(group, new_group);
cnt = group[a[n - 1]] + 1;
step <<= 1;
}
return a;
}
template <typename T>
vector<int> suffix_array(const T &s, int char_bound) {
return suffix_array((int) s.size(), s, char_bound);
}
template <typename T>
vector<int> build_lcp(int n, const T &s, const vector<int> &sa) {
assert((int) sa.size() == n);
vector<int> pos(n);
for (int i = 0; i < n; i++) {
pos[sa[i]] = i;
}
vector<int> lcp(max(n - 1, 0));
int k = 0;
for (int i = 0; i < n; i++) {
k = max(k - 1, 0);
if (pos[i] == n - 1) {
k = 0;
} else {
int j = sa[pos[i] + 1];
while (i + k < n && j + k < n && s[i + k] == s[j + k]) {
k++;
}
lcp[pos[i]] = k;
}
}
return lcp;
}
template <typename T>
vector<int> build_lcp(const T &s, const vector<int> &sa) {
return build_lcp((int) s.size(), s, sa);
}
typedef long long ll;
const int p=998244353;
int po(int a,int b) {if(b==0) return 1; if(b==1) return a; if(b%2==0) {int u=po(a,b/2);return (u*1LL*u)%p;} else {int u=po(a,b-1);return (a*1LL*u)%p;}}
int inv(int x) {return po(x,p-2);}
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <immintrin.h>
#include <algorithm>
#include <cstdint>
#include <cstdio>
#include <cstring>
#include <vector>
constexpr std::uint32_t MOD = 998244353, PRIMITIVE_ROOT = 3;
const unsigned int MAX_N = 524288;
std::uint32_t mod_mul(std::uint32_t a, std::uint32_t b) { return static_cast<std::uint64_t>(a) * b % MOD; }
std::uint32_t pow(std::uint32_t a, std::uint32_t b) {
std::uint32_t ret = 1;
while (b) {
if (b & 1) ret = mod_mul(ret, a);
a = mod_mul(a, a);
b >>= 1;
}
return ret;
}
__m256i mod_add_simd(__m256i a, __m256i b) {
__m256i c = _mm256_add_epi32(a, b);
__m256i d = _mm256_sub_epi32(c, _mm256_set1_epi32(MOD));
__m256i mask = _mm256_cmpgt_epi32(_mm256_set1_epi32(0), d);
return _mm256_blendv_epi8(d, c, mask);
}
__m256i mod_sub_simd(__m256i a, __m256i b) {
__m256i c = _mm256_sub_epi32(a, b);
__m256i d = _mm256_add_epi32(c, _mm256_set1_epi32(MOD));
__m256i mask = _mm256_cmpgt_epi32(_mm256_set1_epi32(0), c);
return _mm256_blendv_epi8(c, d, mask);
}
__m256i reduce_simd(__m256i a) {
__m256i b = _mm256_sub_epi32(a, _mm256_set1_epi32(MOD));
__m256i mask = _mm256_cmpgt_epi32(_mm256_set1_epi32(0), b);
return _mm256_blendv_epi8(b, a, mask);
}
__m256i add_simd(__m256i a, __m256i b) { return _mm256_add_epi32(a, b); }
__m256i sub_simd(__m256i a, __m256i b) {
__m256i c = _mm256_sub_epi32(a, b);
return _mm256_add_epi32(c, _mm256_set1_epi32(MOD));
}
__m256i mulhi_simd(__m256i a, __m256i b) {
__m256i a0 = _mm256_unpacklo_epi32(a, a);
__m256i a1 = _mm256_unpackhi_epi32(a, a);
__m256i b0 = _mm256_unpacklo_epi32(b, b);
__m256i b1 = _mm256_unpackhi_epi32(b, b);
__m256i c0 = _mm256_mul_epu32(a0, b0);
__m256i c1 = _mm256_mul_epu32(a1, b1);
return (__m256i)_mm256_shuffle_ps((__m256)c0, (__m256)c1, _MM_SHUFFLE(3, 1, 3, 1));
}
struct ConstMulSimd {
__m256i a;
__m256i a_div;
explicit ConstMulSimd(std::uint32_t a) : a(_mm256_set1_epi32(a)) { a_div = _mm256_set1_epi32((std::uint64_t(a) << 32) / MOD); }
ConstMulSimd(std::uint32_t a0, std::uint32_t a1, std::uint32_t a2, std::uint32_t a3, std::uint32_t a4, std::uint32_t a5, std::uint32_t a6, std::uint32_t a7) {
a = _mm256_setr_epi32(a0, a1, a2, a3, a4, a5, a6, a7);
std::uint32_t a_div0, a_div1, a_div2, a_div3, a_div4, a_div5, a_div6, a_div7;
a_div0 = (std::uint64_t(a0) << 32) / MOD;
a_div1 = (std::uint64_t(a1) << 32) / MOD;
a_div2 = (std::uint64_t(a2) << 32) / MOD;
a_div3 = (std::uint64_t(a3) << 32) / MOD;
a_div4 = (std::uint64_t(a4) << 32) / MOD;
a_div5 = (std::uint64_t(a5) << 32) / MOD;
a_div6 = (std::uint64_t(a6) << 32) / MOD;
a_div7 = (std::uint64_t(a7) << 32) / MOD;
a_div = _mm256_setr_epi32(a_div0, a_div1, a_div2, a_div3, a_div4, a_div5, a_div6, a_div7);
}
__m256i mul(__m256i b) {
__m256i q = mulhi_simd(a_div, b);
__m256i c = _mm256_mullo_epi32(a, b);
__m256i qm = _mm256_mullo_epi32(q, _mm256_set1_epi32(MOD));
__m256i r = _mm256_sub_epi32(c, qm);
return r;
}
__m256i mul_mod(__m256i b) {
__m256i r = mul(b);
return reduce_simd(r);
}
};
void ntt(unsigned int n, std::uint32_t *a) {
std::uint32_t w = pow(PRIMITIVE_ROOT, (MOD - 1) / n);
unsigned int m = n;
while (m >= 16) {
unsigned int mh = m / 2;
std::uint32_t w0, w1, w2, w3, w4, w5, w6, w7, w8;
w0 = 1;
w1 = w;
w2 = mod_mul(w1, w1);
w3 = mod_mul(w2, w1);
w4 = mod_mul(w2, w2);
w5 = mod_mul(w4, w1);
w6 = mod_mul(w4, w2);
w7 = mod_mul(w4, w3);
w8 = mod_mul(w4, w4);
ConstMulSimd wi_mul(w0, w1, w2, w3, w4, w5, w6, w7);
for (unsigned int i = 0; i < n; i += m) {
std::uint32_t wj = 1;
for (unsigned int j = 0; j < mh; j += 8) {
unsigned int j0 = i + j, j1 = j0 + mh;
__m256i x0 = _mm256_load_si256(reinterpret_cast<__m256i *>(a + j0));
__m256i x1 = _mm256_load_si256(reinterpret_cast<__m256i *>(a + j1));
__m256i y0 = mod_add_simd(x0, x1);
__m256i y1 = wi_mul.mul(sub_simd(x0, x1));
ConstMulSimd wj_mul(wj);
y1 = wj_mul.mul_mod(y1);
_mm256_store_si256(reinterpret_cast<__m256i *>(a + j0), y0);
_mm256_store_si256(reinterpret_cast<__m256i *>(a + j1), y1);
wj = mod_mul(wj, w8);
}
}
m = mh;
w = w2;
}
std::uint32_t w0, w1, w2, w3;
w0 = 1;
w1 = w;
w2 = mod_mul(w1, w1);
w3 = mod_mul(w2, w1);
ConstMulSimd mul_1(1, 1, 1, 1, w0, w1, w2, w3), mul_2(1, 1, w0, w2, 1, 1, w0, w2);
for (unsigned int i = 0; i < n; i += 8) {
__m256i x00, x01, x10, x11, x20, x21, x30, x31, x40, x41, x50, x51, x6;
x00 = _mm256_load_si256(reinterpret_cast<__m256i *>(a + i));
x01 = _mm256_permute4x64_epi64(x00, 0b01001110);
x10 = add_simd(x00, x01);
x11 = sub_simd(x01, x00);
x20 = mul_1.mul_mod(_mm256_blend_epi32(x10, x11, 0b11110000));
x21 = _mm256_shuffle_epi32(x20, 0b01001110);
x30 = add_simd(x20, x21);
x31 = sub_simd(x21, x20);
x40 = mul_2.mul_mod(_mm256_blend_epi32(x30, x31, 0b11001100));
x41 = _mm256_shuffle_epi32(x40, 0b10110001);
x50 = add_simd(x40, x41);
x51 = sub_simd(x41, x40);
x6 = reduce_simd(_mm256_blend_epi32(x50, x51, 0b10101010));
_mm256_store_si256(reinterpret_cast<__m256i *>(a + i), x6);
}
}
void intt(unsigned int n, std::uint32_t *a) {
std::vector<std::uint32_t> w_vec;
std::uint32_t w = pow(PRIMITIVE_ROOT, MOD - 1 - (MOD - 1) / n);
for (unsigned int i = n; i >= 16; i >>= 1) {
w_vec.push_back(w);
w = mod_mul(w, w);
}
std::uint32_t w0, w1, w2, w3;
w0 = 1;
w1 = w;
w2 = mod_mul(w1, w1);
w3 = mod_mul(w2, w1);
ConstMulSimd mul_1(1, 1, 1, 1, w0, w1, w2, w3), mul_2(1, 1, w0, w2, 1, 1, w0, w2);
for (unsigned int i = 0; i < n; i += 8) {
__m256i x00, x01, x10, x11, x20, x21, x30, x31, x40, x41, x50, x51, x6;
x00 = _mm256_load_si256(reinterpret_cast<__m256i *>(a + i));
x01 = _mm256_shuffle_epi32(x00, 0b10110001);
x10 = add_simd(x00, x01);
x11 = sub_simd(x01, x00);
x20 = mul_2.mul_mod(_mm256_blend_epi32(x10, x11, 0b10101010));
x21 = _mm256_shuffle_epi32(x20, 0b01001110);
x30 = add_simd(x20, x21);
x31 = sub_simd(x21, x20);
x40 = mul_1.mul_mod(_mm256_blend_epi32(x30, x31, 0b11001100));
x41 = _mm256_permute4x64_epi64(x40, 0b01001110);
x50 = add_simd(x40, x41);
x51 = sub_simd(x41, x40);
x6 = reduce_simd(_mm256_blend_epi32(x50, x51, 0b11110000));
_mm256_store_si256(reinterpret_cast<__m256i *>(a + i), x6);
}
unsigned int m = 16;
while (m <= n) {
unsigned int mh = m / 2;
std::uint32_t w = w_vec.back();
w_vec.pop_back();
std::uint32_t w0, w1, w2, w3, w4, w5, w6, w7, w8;
w0 = 1;
w1 = w;
w2 = mod_mul(w1, w1);
w3 = mod_mul(w2, w1);
w4 = mod_mul(w2, w2);
w5 = mod_mul(w4, w1);
w6 = mod_mul(w4, w2);
w7 = mod_mul(w4, w3);
w8 = mod_mul(w4, w4);
ConstMulSimd wi_mul(w0, w1, w2, w3, w4, w5, w6, w7);
for (unsigned int i = 0; i < n; i += m) {
std::uint32_t wj = 1;
for (unsigned int j = 0; j < mh; j += 8) {
unsigned int j0 = i + j, j1 = j0 + mh;
__m256i x0 = _mm256_load_si256(reinterpret_cast<__m256i *>(a + j0));
__m256i x1 = _mm256_load_si256(reinterpret_cast<__m256i *>(a + j1));
x1 = wi_mul.mul_mod(x1);
ConstMulSimd wj_mul(wj);
x1 = wj_mul.mul_mod(x1);
__m256i y0 = mod_add_simd(x0, x1);
__m256i y1 = mod_sub_simd(x0, x1);
_mm256_store_si256(reinterpret_cast<__m256i *>(a + j0), y0);
_mm256_store_si256(reinterpret_cast<__m256i *>(a + j1), y1);
wj = mod_mul(wj, w8);
}
}
m *= 2;
}
std::uint32_t n_inv = pow(n, MOD - 2);
ConstMulSimd mul_n_inv(n_inv);
for (unsigned int i = 0; i < n; i += 8) {
__m256i x0 = _mm256_load_si256(reinterpret_cast<__m256i *>(a + i));
_mm256_store_si256(reinterpret_cast<__m256i *>(a + i), mul_n_inv.mul_mod(x0));
}
}
void convolution(unsigned int n, std::uint32_t *a, std::uint32_t *b) {
ntt(n, a);
ntt(n, b);
for (unsigned int i = 0; i < n; i++) {
a[i] = mod_mul(a[i], b[i]);
}
intt(n, a);
}
struct IO {
const static unsigned int MAX_STDIO_SIZE = 10 * 2 * MAX_N + 14;
char stdio_buf[MAX_STDIO_SIZE];
std::uint32_t char_arr_to_int(std::uint64_t x) {
x = (x >> 8) + x * 10;
x = ((x >> 16) & 0x000000FF000000FFull) + (x & 0x000000FF000000FFull) * 100;
x = (x >> 32) + x * 10000;
return x & 0xFFFFFFFFull;
}
std::uint64_t int_to_char_arr(std::uint32_t x) {
std::uint64_t r = x, q;
q = ((r * 109951163) & 0xFFFFFF0000000000ull) >> 40;
r = (r << 32) - q * 42949672959999ull;
q = ((r * 10486) & 0xFFF00000FFF00000ull) >> 20;
r = (r << 16) - q * 6553599ull;
q = ((r * 103) & 0xFC00FC00FC00FC00ull) >> 10;
r = (r << 8) - q * 2559ull;
return r;
}
std::uint32_t read_int(char *&buf) {
std::uint64_t x = *reinterpret_cast<std::uint64_t *>(buf);
std::uint64_t space = ((x + 0x1010101010101010ull) & 0x4040404040404040) ^ 0x4040404040404040;
if (space == 0) {
std::uint32_t res = char_arr_to_int(x - 0x3030303030303030ull);
if (buf[8] <= ' ') {
buf += 9;
} else {
res = res * 10 + (buf[8] - '0');
buf += 10;
}
return res;
}
unsigned int space_pos = __builtin_ffsll(space);
std::uint64_t mask = (1ULL << (space_pos - 7)) - 1;
std::uint32_t res = char_arr_to_int(((x - 0x3030303030303030ull) & mask) << (71 - space_pos));
buf += (space_pos + 1) >> 3;
return res;
}
void read(unsigned int &n, unsigned int &m, std::uint32_t *a, std::uint32_t *b) {
std::fread(stdio_buf, 1, MAX_STDIO_SIZE, stdin);
char *buf = stdio_buf;
n = read_int(buf);
m = read_int(buf);
for (unsigned int i = 0; i < n; i++) {
a[i] = read_int(buf);
}
for (unsigned int i = 0; i < m; i++) {
b[i] = read_int(buf);
}
}
void write_int(char *&buf, std::uint32_t x) {
constexpr std::uint32_t eight_digit = 100000000;
if (x >= eight_digit) [[likely]] {
std::uint32_t upper = x / eight_digit, lower = x % eight_digit;
*buf = '0' + upper;
buf++;
*reinterpret_cast<std::uint64_t *>(buf) = int_to_char_arr(lower) + 0x3030303030303030ull;
buf += 8;
} else {
std::uint64_t char_arr = int_to_char_arr(x);
unsigned int padding = __builtin_ctzll(char_arr + (1ull << 63)) >> 3, len = 8 - padding;
char_arr += 0x3030303030303030ull;
*reinterpret_cast<std::uint64_t *>(buf) = char_arr >> (padding << 3);
buf += len;
}
*buf = ' ';
buf++;
}
void write(unsigned int n, std::uint32_t *a) {
char *buf = stdio_buf;
for (unsigned int i = 0; i < n; i++) {
write_int(buf, a[i]);
}
unsigned int len = buf - stdio_buf;
std::fwrite(stdio_buf, 1, len, stdout);
}
} io;
alignas(32) static std::uint32_t v1[MAX_N * 2], v2[MAX_N * 2];
template<int M, int K, int G> struct Fft {
// 1, 1/4, 1/8, 3/8, 1/16, 5/16, 3/16, 7/16, ...
int g[1 << (K - 1)];
constexpr Fft() : g() { //if tl constexpr...
static_assert(K >= 2, "Fft: K >= 2 must hold");
g[0] = 1;
g[1 << (K - 2)] = G;
for (int l = 1 << (K - 2); l >= 2; l >>= 1) {
g[l >> 1] = (static_cast<long long>(g[l]) * g[l]) % M;
}
assert((static_cast<long long>(g[1]) * g[1]) % M == M - 1);
for (int l = 2; l <= 1 << (K - 2); l <<= 1) {
for (int i = 1; i < l; ++i) {
g[l + i] = (static_cast<long long>(g[l]) * g[i]) % M;
}
}
}
void fft(vector<int> &x) const {
const int n = x.size();
assert(!(n & (n - 1)) && n <= 1 << K);
for (int h = __builtin_ctz(n); h--; ) {
const int l = 1 << h;
for (int i = 0; i < n >> 1 >> h; ++i) {
for (int j = i << 1 << h; j < ((i << 1) + 1) << h; ++j) {
const int t = (static_cast<long long>(g[i]) * x[j | l]) % M;
if ((x[j | l] = x[j] - t) < 0) x[j | l] += M;
if ((x[j] += t) >= M) x[j] -= M;
}
}
}
for (int i = 0, j = 0; i < n; ++i) {
if (i < j) std::swap(x[i], x[j]);
for (int l = n; (l >>= 1) && !((j ^= l) & l); ) {}
}
}
vector<int> convolution(const vector<int> &a, const vector<int> &b) const {
if(a.empty() || b.empty()) return {};
const int na = a.size(), nb = b.size();
int n, invN = 1;
for (n = 1; n < na + nb - 1; n <<= 1) invN = ((invN & 1) ? (invN + M) : invN) >> 1;
vector<int> x(n, 0), y(n, 0);
std::copy(a.begin(), a.end(), x.begin());
std::copy(b.begin(), b.end(), y.begin());
fft(x);
fft(y);
for (int i = 0; i < n; ++i) x[i] = (((static_cast<long long>(x[i]) * y[i]) % M) * invN) % M;
std::reverse(x.begin() + 1, x.end());
fft(x);
x.resize(na + nb - 1);
return x;
}
};
Fft<998244353,23,31> muls;
vector<int> operator *(vector<int> v1,vector<int> v2)
{
return muls.convolution(v1,v2);
}
int32_t main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
/*string s="abbaaaf";
vector<int> sa=suffix_array(s,256);
vector<int> lc=build_lcp(s,sa);
for(int i:sa) cout<<i<<' '; cout<<endl;
for(int i:lc) cout<<i<<' '; cout<<endl;*/
int t;cin>>t;
while(t--)
{
int n,m;cin>>n;
string s1,s2;cin>>s1;
s2="helloworld";
m=s2.size();
string s0=s1;
bool ok[n-m+1];for(int i=0;i<=n-m;++i) ok[i]=true;
int h=1;while(h<=n+m) h*=2;
for(char c='a';c<='z';++c)
{
int cnt=0;
for(int i=0;i<h;++i) {v1[i]=0;v2[i]=0;}
for(int i=0;i<n;++i) v1[n-i-1]=(s1[i]==c || s1[i]=='?');
for(int i=0;i<m;++i) {v2[i]=(s2[i]==c);cnt+=v2[i];}
if(h>=2000) convolution(h, v1, v2);
else
{
vector<int> v11;for(int i=0;i<n;++i) v11.push_back(v1[i]);
vector<int> v21;for(int i=0;i<m;++i) v21.push_back(v2[i]);
vector<int> v31=v11*v21;
for(int i=m-1;i<=n-1;++i) v1[i]=v31[i];
}
for(int i=m-1;i<=n-1;++i)
{
ok[n-i-1]&=(v1[i]==cnt);
}
}
for(int i=0;i<s1.size();++i) if(s1[i]=='?') s1[i]='a';
string s=s1;s.push_back('$');s+=s2;
if(accumulate(ok,ok+n-m+1,0LL)==0)
{
cout<<(-1)<<'\n';
continue;
}
vector<int> sa=suffix_array(s,256);
vector<int> lc=build_lcp(s,sa);
vector<int> pos(s.size());
for(int i=0;i<s.size();++i)
{
pos[sa[i]]=i;
}
int lcsz=lc.size();
for(int i=0;i<lcsz;++i)
{
sp[i][0]=lc[i];
}
for(int j=1;j<20;++j)
{
for(int i=0;i<=lcsz-(1<<j);++i)
{
sp[i][j]=min(sp[i][j-1],sp[i+(1<<(j-1))][j-1]);
}
}
int l1=0;int l2=s1.size()+1;
int inf=1e9;
/*string stupid;
{
for(int i=0;i<=n-m;++i) if(ok[i])
{
string ans=s1.substr(0,i);ans+=s2;ans+=s1.substr(i+m,n-m-i);
if(stupid.empty()) stupid=ans;
else stupid=min(stupid,ans);
}
}*/
auto get=[&](int i,int j)
{
int i1=i;int j1=j;
i=pos[i];j=pos[j];
if(i>j) swap(i,j);
if(i==j) return inf;
int o=31-__builtin_clz(j-i);
return min(sp[i][o],sp[j-(1<<o)][o]);
};
auto cmp=[&](int i,int j)->bool
{
if(i==j) return false;
bool sw=false;
if(i>j) {swap(i,j);sw=true;}
{
if(j-i<s2.size())
{
int pos1=get(i,l2);
if(pos1<j-i)
{
return (s[l2+pos1]<s[i+pos1])^sw;
}
int pos2=get(l2,l2+j-i);
if(pos2<m-(j-i))
{
return (s[l2+j-i+pos2]<s[l2+pos2])^sw;
}
int pos3=get(i+m,l2+m-(j-i));
if(pos3<(j-i))
{
return (s[i+m+pos3]<s[l2+m-(j-i)+pos3])^sw;
}
return false;
}
else
{
int pos1=get(i,l2);
if(pos1<m)
{
return (s[l2+pos1]<s[i+pos1])^sw;
}
int pos2=get(j,l2);
if(pos1<m)
{
return (s[j+pos1]<s[l2+pos1])^sw;
}
return false;
}
}
};
vector<int> v;
for(int i=0;i<=n-m;++i) if(ok[i]) v.push_back(i);
int pos1=(*min_element(v.begin(),v.end(),cmp));
string ans=s1.substr(0,pos1);
ans+=s2;
ans+=s1.substr(pos1+m,n-m-pos1);
/*if(ans!=stupid)
{
cout<<s0<<' '<<s1<<' '<<s2<<endl;
cout<<ans<<' '<<stupid<<endl;
}
assert(ans==stupid);*/
cout<<ans<<'\n';
}
return 0;
}
/*
1
12 3
t?t?r???g?s?
kog
*/