#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#include "brperm.h"
string str;int lol[20][500001];
mt19937 rng;
void init(int n, const char s[]){
    rng.seed(time(0));
    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;
    for(int e = 0;e<1000;e++){
    int l = rng()%(1<<k);
        if(str[l+i]!=str[lol[k][l]+i]){
            return 0;
        }
    }
    return 1;
}