#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2,bmi,bmi2")
#include "brperm.h"
string str;int lol[20][500001];
void init(int n, const char s[]){
    for(int i = 0;i<n;i++){
        str+=s[i];
    }
    for(int k = 0;(1<<k)<=n;k++){
        for(int i = 0;i<(1<<k);i++){
            lol[k][i] = 0;
            for(int j = 0;j<k;j++){
                if(i&(1<<j)){
                    lol[k][i]|=(1<<(k-j-1));
                }
            }
        }
    }
}
int query(int i , int k){
    if(i+(1<<k)-1>str.size())return 0;
    for(int l = i;l<i+(1<<k);l++){
        if(str[l]!=str[lol[k][l-i]+i]){
            return 0;
        }
    }
    return 1;
}