# 某島

… : "…アッカリ～ン . .. . " .. .
June 9, 2012

## ？？？？

### Analysis:

/*
Result: 10201418	11996	Jewel Magic	Accepted	C++	4.968	2012-06-07 17:24:29
Algorithm: Splay+Hash+Bianry Search.
*/

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std ;

typedef long long LL ;

#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fi(i,a,b) for(int i=a;i>=b;i--)

const int MaxN = 200009 ;
const int MOD = 3214567 ;
LL Pow[MaxN] ;

struct Tnode;          // Splay中的一個結點
typedef Tnode *Tsplay; // 地址(標記預留內存使用情況)
Tsplay null;           // 空結點標記
struct Tnode{
Tnode *l, *r;
int size, key;
bool flip ;
LL h1, h2 ;
Tnode() {};
Tnode(int value): l(null), r(null), size(1), h1(value), h2(value), key(value), flip(false) {};
};
Tnode seg[MaxN*4]; // 開雙倍內存預留
Tsplay newTnode;   // 標記預留內存使用到的位置
/*Renew t's inf from t->l and t->r*/
void Up  (Tsplay t){
t->size = (t->l->size)+(t->r->size)+1 ;
t->h1 = ((((t->l->h1) * Pow[1] + (t->key)) % MOD) * Pow[t->r->size] + (t->r->h1)) % MOD ;
t->h2 = ((((t->r->h2) * Pow[1] + (t->key)) % MOD) * Pow[t->l->size] + (t->l->h2)) % MOD ;
// For ex: size, min, max...
}
/*Renew (t->l and t->r)'s inf from t*/
void Down(Tsplay t){
// For ex: add, flip
if ( t->l != null ) {
if ( t->flip ) { swap(t->l->h1,t->l->h2); swap(t->l->l,t->l->r); t->l->flip^=1; }
}
if ( t->r != null ) {
if ( t->flip ) { swap(t->r->h1,t->r->h2); swap(t->r->l,t->r->r); t->r->flip^=1; }
}
t->flip = 0;
}
void RL(Tsplay &t) { Tsplay s=t->r; t->r=s->l; s->l=t; Up(t); Up(s); t=s; }
void RR(Tsplay &t) { Tsplay s=t->l; t->l=s->r; s->r=t; Up(t); Up(s); t=s; }
void Splay(Tsplay &root, int k) {
if (root == null) return;
Down(root);
if      (k-1==root->l->size);     // Here it is!
else if (k  <=root->l->size){     // On the left sub_tree.
Splay(root->l,k);
RR(root);
} else {                          // On the right.
Splay(root->r,k-root->l->size-1);
RL(root);
}
}
/*operate in segment [p1,p2]*/
void Reverse(Tsplay &root, int p1, int p2) {
Splay(root,p1-1); Splay(root, p2+1);
swap(root->l->r->h1 , root->l->r->h2);
swap(root->l->r->l , root->l->r->r);
root->l->r->flip ^= 1;
// Do some change and mark.
}
/*Insert a new element with key(k) after the p_th element*/
void Insert(Tsplay &root, int p, int k) {
Tsplay t=++newTnode; *t=Tnode(k);
Splay(root, p); t->r=root->r; root->r=t;
Up(t); Up(root);
}
/*Delete the p_th element in the seq.*/
void Delete(Tsplay &root, int p) {
Splay(root,p); Splay(root->r,1);
root->r->l=root->l; root=root->r;
Up(root);
}
LL Hash(Tsplay &root, int p1, int p2) {
Splay(root,p1-1); Splay(root, p2+1);
return root->l->r->h1;
}
/*************************************************/
Tsplay root;
/*Init Splay: Insert TWO node with key=INF*/
void InitSplay(Tsplay &root) {
newTnode=seg; null=seg;
*null=Tnode(-1); null->size=0;
root=++newTnode;
Tsplay tmp=++newTnode;
*root=Tnode(-1); *tmp=Tnode(-1);
root->r=tmp; root->size=2;
}

int N , M ;
int main() {
Pow[0] = 1LL ;
fo(i,1,200000) Pow[i]=(Pow[i-1]*13) % MOD;
while (scanf("%d %d", &N, &M) != EOF) {
InitSplay(root) ;
getchar(); char r ; fo(i,1,N) {
r = getchar() ; Insert(root,i,r-'0') ;
}
while ( M -- ) {
int o , p1 , p2 , c ; scanf("%d", &o) ;
if ( o == 1 ) { scanf("%d%d", &p1, &c); Insert(root,p1+1,c) ; N ++ ; }
if ( o == 2 ) { scanf("%d", &p1) ; Delete(root,p1+1) ; N -- ; }
if ( o == 3 ) { scanf("%d%d", &p1, &p2) ; Reverse(root,p1+1,p2+1) ; }
if ( o == 4 ) {
scanf("%d%d", &p1, &p2);
int k = 1 ; while ( p1 + k*2 - 1 <= N && p2 + k*2 - 1 <= N ) k *= 2 ;
int ans = 0 ;
while ( k > 0 ) {
if ( p1+k-1 > N || p2+k-1 > N ) { k /= 2 ; continue ; }
if ( Hash(root,p1+1,p1+k-1+1) == Hash(root,p2+1,p2+k-1+1) ) {
ans += k ;
p1 += k , p2 += k ;
}
k /= 2 ;
}
printf("%d\n", ans);
}
}
}
}