// #pragma GCC optimize("O3, unroll-loops, Ofast")
#include "brperm.h"
#include<bits/stdc++.h>
#include<random>
#include<chrono>
#define int long long
using namespace std;
const int MAXN = 500000;
const int ITERATIONS = 1000;
int rev(int a, int p){
int r = 0;
int p2 = 1 << p;
for(int i = 0; i < p; i++){
int bit = (a & (1<<i)) > 0;
r += (1<<(p-i-1)) * bit;
}
return r;
}
char str[MAXN];
int n;
mt19937 rng;
void init(int32_t N, const char arr[]) {
rng = mt19937(chrono::steady_clock::now().time_since_epoch().count());
n = N;
for(int i = 0; i < n; i++){
str[i] = arr[i];
}
return;
}
int32_t query(int32_t l, int32_t k) {
int p2 = 1 << k;
int r = l +p2-1;
if(l + p2 > n) return 0;
bool valid = true;
// for(int i = l; i < l+p2; i++){
// int np = rev(i-l, k)+l;
// if(str[np] != str[i]) return 0;
// }
for(int t = 0; t < ITERATIONS; t++){
int i = uniform_int_distribution<int>(0, p2-1)(rng) + l;
int np = rev(i-l, k)+l;
if(str[np] != str[i]) {
return 0;
}
}
return valid;
}
