#include "brperm.h"
#include <bits/stdc++.h>
#define f1(i,n) for(int i = 1; i <= n; i++)
#define H unsigned long long
using namespace std;
const int maxn = 5e5+5, base = 31, LG = 19;
int N;
H hs[maxn], pw[maxn];
H vrev[2][LG+1][maxn];
bool ans[LG][maxn];
H getHash(int l, int r){
return hs[r] - hs[l - 1] * pw[r - l + 1];
}
void init(int n, const char s[]) {
N = n;
pw[0] = 1;
f1(i,n){
// int idx = (i + 1) >> 1;
// hs[i&1][idx] = hs[i&1][idx-1] * base + s[i-1] - 'a' + 1;
hs[i] = hs[i-1] * base + s[i-1] - 'a' + 1;
pw[i] = pw[i-1] * base;
for(int j = 0; j < LG; j++) vrev[0][j][i] = s[i-1] - 'a' + 1;
}
f1(b, LG-1){
for(int j = 0; j < LG; j++){
f1(i,n){
if(i + (1LL << (b)) - 1 > n) break;
int ptr = i + (1 << (b - 1));
vrev[b&1][j][i] = (vrev[b&1^1][j+1][i] * pw[1 << j] + vrev[b&1^1][j+1][ptr]);
if(j == 0){
// cout << "HERE: " << vrev[b&1^1][j+1][i] << ' ' << vrev[b&1^1][j+1][ptr] << '\n';
// cout << "? " << i << ' ' << i + (1 << b) - 1 << ' ';
// cout << vrev[b&1][j][i] << ' ' << getHash(i, i + (1 << b) - 1) << endl;
ans[b][i] = (vrev[b&1][j][i] == getHash(i, i + (1 << b) - 1));
}
}
}
}
}
int query(int i, int k) {
i++;
if(i + (1 << k) - 1 > N) return 0;
if(k == 0) return 1;
return ans[k][i];
}
