#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#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++){
            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;
    int r =i+(1<<k);
    for(int l = i;l<r;l++){
        if(str[l]!=str[lol[k][l-i]+i]){
            return 0;
        }
    }
    return 1;
}