//#include "grader.cpp"
#include "brperm.h"
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
#define ull unsigned long long
int n;
const int MAXN=5e5,MAXLG=19;
ull sparse[MAXLG][MAXN];
ull suf[MAXLG][MAXN+1];
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ull base;
ull power[MAXLG];
ull binpow(ull n,int k){
ull curr=1;
for(;k;k>>=1){
if(k&1){
curr*=n;
}
n*=n;
}
return curr;
}
void init(int N,const char s[]){
n=N;
base=177013;
power[0]=base;
for(int i=1;i<MAXLG;i++){
power[i]=(power[i-1]*power[i-1]);
}
for(int i=0;i<MAXLG;i++){
suf[i][n]=0;
for(int j=n-1;j>=0;j--){
suf[i][j]=(suf[i][j+1]*power[i])+s[j];
}
}
for(int j=0;j<n;j++){
sparse[0][j]=s[j];
}
for(int i=1;i<MAXLG;i++){
for(int j=0;j+(1<<i)<=n;j++){
sparse[i][j]=sparse[i-1][j]+(sparse[i-1][j+(1<<(i-1))]*power[MAXLG-1-i]);
}
}
// for(int i=0;i<MAXLG;i++){
// for(int j=0;j+(1<<i)<=n;j++){
// cout << i << ' ' << j << ' ' << sparse[i][j] << endl;
// }
// }
}
int query(int i,int k){
if(i+(1<<k)>n){
return 0;
}
ull curr=sparse[k][i];
ull curr2=suf[MAXLG-1-k][i]-(suf[MAXLG-1-k][i+(1<<k)]*binpow(power[MAXLG-1-k],1<<k));
if(curr==curr2){
return 1;
}
return 0;
}
