#include "brperm.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 5e5 + 5 , LG = 20 , P = 131;
int t; ull p[LG] = {P} , f[LG][N] , h[LG][N] , iv[LG][N];
ull Qpow(ull x , ull p = (1llu << 63) - 1)
{
  ull res = 1;
  for(; p ; p >>= 1 , x = x * x)
    if(p & 1)res = x * res;
  return res;
}
ull Get(int k , int l , int r){return (h[k][r] - h[k][l - 1]) * iv[t - k][l - 1];}
void init(int n, const char s[]) {

  t = __lg(n);
  for(int i = 1 ; i <= t ; i++)
    p[i] = p[i - 1] * p[i - 1];
  for(int i = 0 ; i <= t ; i++)
  {
    iv[i][0] = 1; 
    iv[i][1] = Qpow(p[i]);
    for(int j = 2 ; j <= n ; j++)
      iv[i][j] = iv[i][j - 1] * iv[i][1];
  }
  for(int i = 1 ; i <= n ; i++)f[0][i] = s[i - 1];
  for(int i = 1 ; i <= t ; i++)
    for(int j = 1 ; j + (1 << i) - 1 <= n ; j++)
      f[i][j] = f[i - 1][j] + p[t - i] * f[i - 1][j + (1 << (i - 1))];

  for(int i = 0 ; i <= t ; i++)
  {
    ull pw = 1;
    for(int j = 1 ; j <= n ; j++)
    {
      h[i][j] = h[i][j - 1] + s[j - 1] * pw;
      pw = pw * p[t - i];
    }
  }
  return;
}
int query(int l, int k) 
{
  int r = (++l) + (1 << k) - 1;
  return f[k][l] == Get(k , l , r);
}