#include <bits/stdc++.h>
#include "brperm.h"
using namespace std;
const int nmax = 500005;
int n;
char c[nmax];
int revpre[nmax][20];
int rev(int x, int k) {
int res = 0,cnt = 0;
for (int i = k - 1; i >= 0; i--) {
if (x & (1 << i)) res += (1 << cnt);
cnt++;
}
return res;
}
void init(int N, const char C[]) {
n = N;
for (int k = 0; k < 20; k++) {
for (int i = 0; i < n; i++) {
revpre[i][k] = rev(i,k);
}
}
for (int i = 0; i < N; i++) {
c[i] = C[i];
}
}
int query(int i, int k) {
if (i + (1 << k) - 1 >= n) return 0;
int limit = i + (1 << k) - 1;
for (int j = i; j <= limit; j++) {
if (c[j] != c[revpre[j - i][k] + i]) return 0;
}
return 1;
}
