#include "brperm.h"
#include "bits/stdc++.h"
namespace {
using i64 = long long;
template<typename T>
T power(T a, i64 b) {
T res = 1;
while(b) {
if(b & 1) {
res *= a;
}
a *= a;
b >>= 1;
}
return res;
}
constexpr int md = 998244353;
struct MInt {
int val;
MInt() : val(0) {}
template<typename T>
MInt(T v) {
if(-md <= v && v < md) {
val = v;
} else {
val = v % md;
}
if(val < 0) {
val += md;
}
}
int operator() () { return val; }
MInt operator+= (MInt rhs) {
if((val += rhs.val) >= md) {
val -= md;
}
return *this;
}
MInt operator-= (MInt rhs) {
if((val -= rhs.val) < 0) {
val += md;
}
return *this;
}
MInt operator*= (MInt rhs) {
val = (int)(1LL * val * rhs.val % md);
return *this;
}
MInt inv() {
return power(*this, md - 2);
}
MInt operator/= (MInt rhs) {
return *this *= rhs.inv();
}
bool operator== (MInt rhs) const {
return val == rhs.val;
}
bool operator!= (MInt rhs) const {
return val != rhs.val;
}
};
MInt operator+ (MInt lhs, MInt rhs) {
return lhs += rhs;
}
MInt operator- (MInt lhs, MInt rhs) {
return lhs -= rhs;
}
MInt operator* (MInt lhs, MInt rhs) {
return lhs *= rhs;
}
MInt operator/ (MInt lhs, MInt rhs) {
return lhs /= rhs;
}
std::ostream& operator<< (std::ostream& os, MInt v) {
return os << v();
}
std::string to_string(MInt x) {
return to_string(x());
}
using Z = MInt;
constexpr int base = 31;
int N;
int LG;
std::string str;
std::vector<Z> powb;
std::vector<std::vector<Z>> pre;
std::vector<std::vector<Z>> f;
};
void init(int n, const char s[]) {
str = s;
N = n;
LG = std::__lg(N);
powb.resize(LG + 1);
powb[0] = base;
for (int i = 1; i <= LG; ++i) {
powb[i] = powb[i - 1] * powb[i - 1];
}
pre.resize(LG + 1);
for (int j = 0; j <= LG; ++j) {
pre[j].resize(N + 1);
for (int i = 0; i < N; ++i) {
pre[j][i + 1] = pre[j][i] * powb[LG - j] + (s[i] - 'a' + 1);
}
}
f.resize(LG + 1);
f[0].resize(N);
for (int i = 0; i < N; ++i) {
f[0][i] = s[i] - 'a' + 1;
}
for (int j = 1; j <= LG; ++j) {
int m = N - (1 << j) + 1;
f[j].resize(m);
for (int i = 0; i < m; ++i) {
f[j][i] = powb[LG - j] * f[j - 1][i] + f[j - 1][i + (1 << (j - 1))];
}
}
// for (int j = 0; j <= LG; ++j) {
// int m = N - (1 << j) + 1;
// for (int i = 0; i < m; ++i) {
// std::cerr << f[j][i] << " \n"[i == m - 1];
// }
// }
return;
}
int query(int i, int k) {
if (i + (1 << k) - 1 >= N) {
return 0;
}
Z sh = pre[k][i + (1 << k)] - pre[k][i] * powb[LG];
// Z sh = 0;
// for (int j = 0; j < (1 << k); ++j) {
// sh = sh * powb[LG - k] + str[i + j] - 'a' + 1;
// std::cerr << sh << ' ';
// }
// std::cerr << '\n';
Z rh = f[k][i];
// std::cerr << "[sh, rh]: " << sh << ' ' << rh << '\n';
return sh == rh;
}
