//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
//#pragma GCC target("bmi,bmi2,popcnt,lzcnt")
//Andrusha Holod did not qualify to IOI 2025 )))
//Hope Andrusha Holod will win IOI 2026
#include "brperm.h"
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cmath>
#include <fstream>
#include <climits>
#include <queue>
#include <algorithm>
#include <stdint.h>
#include <stack>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <cstring> // Для memset
#define endl '\n'
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair < ll, ull > piu;
typedef pair <ll, ll> pii;
typedef pair <ld, ld> pdd;
const ll DIM = 100007;
const ll MXMASK = (1 << 21);
const ll INF = 1e18;
const ll mod = 1e9 + 123;
const ld eps = 0.00000000001;
const ld gr = (sqrt(5) + 1) / 2;
const ll offset = 10000;
const ll Bits = 20;
const ll dx[5] = { -1, -1, 0, 1, 0 };
const ll dy[5] = { -1, 0, -1, 0, 1 };
FILE* stream;
ll getval(char val) {
return val - 'a' + 1;
}
class polyHash {
public:
const ll base = 31;
vector < ll > powll;
vector < ull > powull;
vector < ll > prefll;
vector < ull > prefull;
void count(const string& s) {
ll n = s.length();
powll.resize(n + 7);
powull.resize(n + 7);
prefll.resize(n + 7);
prefull.resize(n + 7);
powll[0] = 1;
powull[0] = 1;
for (int i = 1; i <= n; i++) {
powll[i] = (powll[i - 1] * base) % mod;
powull[i] = (powull[i - 1] * base);
if (powll[i] < 0) powll[i] += mod;
}
prefll[0] = 0;
prefull[0] = 0;
for (int i = 1; i <= n; i++) {
prefll[i] = ((prefll[i - 1] * base) + getval(s[i - 1])) % mod;
prefull[i] = (prefull[i - 1] * base) + getval(s[i - 1]);
if (prefll[i] < 0) prefll[i] += mod;
}
}
piu gethash(ll L, ll R) {
ll len = R - L + 1;
ll hashll = prefll[R] - (powll[len] * prefll[L - 1]) % mod;
//ull hashull = prefull[R] - (powull[len] * prefull[L - 1]);
ull hashull = 0;
if (hashll < 0) hashll += mod;
return { hashll, hashull };
}
piu mergeHash(piu h1, piu h2, ll len) {
piu res;
res.first = (h1.first * powll[len] + h2.first) % mod;
//res.second = h1.second * powull[len] + h2.second;
if (res.first < 0) res.first += mod;
return res;
}
};
polyHash h;
vector < vector < vector < int > > > H;
ll N;
vector < ll > powers(30);
void init(int n, const char s[]) {
N = n;
h.count(s);
ll r = 1, p = 0;
while (2 * r <= n) {
r *= 2;
p++;
}
H.resize(n + 7);
for (int i = 0; i < n + 7; i++) {
H[i].resize(p + 2);
for (int j = 0; j < p + 2; j++) {
H[i][j].resize(p + 2);
}
}
powers[0] = 1;
for (int i = 1; i <= p; i++) powers[i] = (2 * powers[i - 1]) % mod;
for (int i = n - 1; i >= 0; i--) {
for (int k = 0; k <= p; k++) {
for (int j = 0; j <= p; j++) {
//cout << i << " " << k << " " << j << endl;
if (n - i < powers[j] * (powers[k] - 1) + 1) continue;
if (k == 0) H[i][j][k] = h.gethash(i + 1, i + 1).first;
else {
H[i][j][k] = h.mergeHash({ H[i][j + 1][k - 1], 0 }, { H[i + powers[j]][j + 1][k - 1], 0 }, powers[k - 1]).first;
}
}
}
}
}
int query(int i, int k) {
if (i + (1 << k) - 1 >= N) return 0;
if (h.gethash(i + 1, i + powers[k]).first == H[i][0][k]) return 1;
else return 0;
}
