#include "brperm.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+10, LG=19;
const pair<int, int> mod={(int)1e9+7, (int)1e9+9}, base={3636, 6767};
pair<int, int> pw[N];
struct Node{
int sz;
pair<int, int> val;
int il, ir;
Node (int _sz=0, pair<int, int> _val={0, 0}){
sz=_sz, val=_val;
il=0;
ir=0;
}
void merge();
};
Node t[N*4];
int tsz=1;
void Node::merge(){
val={
(t[il].val.first*pw[t[ir].sz].first+t[ir].val.first)%mod.first,
(t[il].val.second*pw[t[ir].sz].second+t[ir].val.second)%mod.second,
};
sz=t[il].sz+t[ir].sz;
}
struct SegmentTree{
void build(int k, int l, int r, char a[]){
if (l==r){
t[k].sz=1;
t[k].val={a[l], a[l]};
return;
}
int mid=(l+r)>>1;
if (!t[k].il) t[k].il=++tsz;
if (!t[k].ir) t[k].ir=++tsz;
build(t[k].il, l, mid, a);
build(t[k].ir, mid+1, r, a);
t[k].merge();
}
void update(int k, int l, int r, int pos, int val){
if (l==r){
t[k].sz=1;
t[k].val={val, val};
return;
}
int mid=(l+r)>>1;
if (pos<=mid){
update(t[k].il, l, mid, pos, val);
}else{
update(t[k].ir, mid+1, r, pos, val);
}
t[k].merge();
}
void swap_node(int k, int l, int r){
if (l==r) return;
swap(t[k].il, t[k].ir);
int mid=(l+r)>>1;
swap_node(t[k].ir, mid+1, r);
t[k].merge();
}
} st;
pair<int32_t, int32_t> val[LG][N], val2[LG][N];
char a[N];
int n;
void init(int32_t _n, const char s[]) {
n=_n;
for (int i=0; i<n; ++i) val[0][i]={s[i], s[i]};
pw[0]={1, 1};
for (int i=1; i<=n; ++i){
pw[i]={
pw[i-1].first*base.first%mod.first,
pw[i-1].second*base.second%mod.second,
};
}
for (int k=1; k<LG; ++k){
for (int i=0; i+(1<<k)-1<n; ++i){
val[k][i]={
(val[k-1][i].first*pw[1<<(k-1)].first+val[k-1][i+(1<<(k-1))].first)%mod.first,
(val[k-1][i].second*pw[1<<(k-1)].second+val[k-1][i+(1<<(k-1))].second)%mod.second,
};
}
}
int kk=0;
while ((1<<(kk+1))<=n) ++kk;
st.build(1, 0, (1<<kk)-1, a);
for (int k=0; k<LG; ++k){
if ((1<<k)>n) break;
a[0]=s[0];
for (int i=1, j=0; i<(1<<k); ++i){
int bit=1<<(k-1);
for (; j&bit; bit>>=1) j^=bit;
j^=bit;
a[j]=s[i];
}
st.build(1, 0, (1<<k)-1, a);
val2[k][0]=t[1].val;
for (int i=1; i+(1<<k)-1<n; ++i){
st.swap_node(1, 0, (1<<k)-1);
st.update(1, 0, (1<<k)-1, (1<<k)-1, s[i+(1<<k)-1]);
val2[k][i]=t[1].val;
}
}
}
int32_t query(int32_t i, int32_t k) {
if (i+(1<<k)-1>=n) return 0;
return val[k][i]==val2[k][i];
}
// mt19937 rng(42);
// int rand(int l, int r){
// return uniform_int_distribution<int>(l, r)(rng);
// }
// char ss[N];
// int32_t main(){
// int nn=5e5;
// for (int i=0; i<nn; ++i) ss[i]=rand('a', 'b');
// init(nn, ss);
// for (int i=0; i<nn; ++i) query(0, rand(0, 15));
// return 0;
// }
