#include "brperm.h"
#include <iostream>
using namespace std;
int const N=5e5+10,LG=20;
bool vis[N][LG],ans[N][LG]={};
string x;
int n;
void init(int N, const char S[])
{
n=N;
for (int i=0;i<n;i++)
x+=S[i];
return;
}
int query(int i, int k)
{
if (i+(1<<k)>n)
return 0;
if (vis[i][k])
return ans[i][k];
vis[i][k]=1;
int len=(1<<k);
for (int j=0;j<len;j++)
{
int op=0;
for (int l=0;l<k;l++)
{
if ((1<<l)&j)
op|=(1<<(k-1-l));
}
if (x[i+j]!=x[i+op])
{
ans[i][k]=0;
return 0;
}
}
ans[i][k]=1;
return ans[i][k];
}
