#include "brperm.h"
// #include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define name "TENBAI"
#define fi first
#define se second
#define endl '\n'
#define setmin(x, y) x = min((x), (y))
#define setmax(x, y) x = max((x), (y))
#define sqr(x) ((x) * (x))
#define all(x) x.begin(), x.end()
mt19937 hdp(chrono::high_resolution_clock::now().time_since_epoch().count());
int rand(int l, int r){return l + ((hdp() % (r - l + 1)) + r - l + 1) % (r - l + 1);}
const int NM = 5e5 + 5;
const int LG = 19;
const int mod = 1e9 + 7;
const int p = 31;
int ex[NM], a[NM], hsh[2][NM][LG], pf[NM], n;
bool b[NM][LG];
void init(int N, const char s[])
{
n = N;
for (int i = 0; i < n; i++)
a[i + 1] = s[i] - 'a' + 1;
ex[0] = 1;
for (int i = 1; i <= n; i++)
{
ex[i] = 1ll * ex[i - 1] * p % mod;
pf[i] = (1ll * pf[i - 1] * p + a[i]) % mod;
for (int j = 0; j < 19; j++)
hsh[0][i][j] = a[i];
}
for (int i = 1; i < 19; i++)
for (int j = 1; j <= n; j++)
for (int k = 0; k <= 18 - i && j + 1ll * ((1 << i) - 1) * (1 << k) <= n; k++)
{
hsh[i & 1][j][k] = (1ll * hsh[i & 1 ^ 1][j][k + 1] * ex[1 << i - 1] + hsh[i & 1 ^ 1][j + (1 << k)][k + 1]) % mod;
if (k == 0)
{
int x = (pf[j + (1 << i) - 1] + mod - 1ll * pf[j - 1] * ex[1 << i] % mod) % mod;
b[j][i] = (x == hsh[i & 1][j][k]);
}
}
}
int query(int i, int k)
{
i++;
if (i + (1 << k) - 1 > n)
return 0;
return b[i][k];
}
