bzoj3217 ALOEXT

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
using namespace std;
namespace Debug{
    Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
    Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
    Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
    #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
    Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;}
    Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
    Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
    Tp I void writeln(Cn Ty& x){write(x),pc('\n');}
}using namespace FastIO;
Cn int N=2e5+10,S=5000,M=N/S+2,P=1048576;
I int RC(){char c=gc();W(c^'I'&&c^'D'&&c^'C'&&c^'F') c=gc();return c=='I'?1:c=='D'?2:c=='C'?3:4;}
int n,m,tot;
vector<int> b[M];
multiset<int> s[M];
#define PA pair<int,int>
#define MP make_pair
#define fi first
#define se second
class TrieTree{
    private:
        int p[S*100][2],cnt,w[S*100];
        #define nw ((v>>i)&1)
    public:
        I void clear(){cnt=1;memset(p,0,sizeof(p));memset(w,0,sizeof(w));}
        I void A(CI v){RI i,u=1;for(i=20;~i;i--) !p[u][nw]&&(p[u][nw]=++cnt),w[p[u][nw]]++,u=p[u][nw];}
        I void K(CI v){RI i,u=1,t;for(i=20;~i;i--) w[p[u][nw]]--,u=p[u][nw];}
        I int Q(CI v){RI i,u=1,X=0;for(i=20;~i;i--) (p[u][nw^1]&&w[p[u][nw^1]])?X+=(1<<i),u=p[u][nw^1]:u=p[u][nw];return X;}
}T[M];
I void H(PA& X,CI v){v>X.fi?X.se=X.fi,X.fi=v:X.se=max(X.se,v);}
I PA G(CI l,CI x,CI y){PA o=MP(0,0);for(auto i=b[l].begin()+x;i!=b[l].begin()+y+1;i++) H(o,*i);return o;}
I int F(CI l,CI x,CI y,CI v){RI mx=0;for(auto i=b[l].begin()+x;i!=b[l].begin()+y+1;i++) mx=max(mx,(*i)^v);return mx;}
I int Z(CI L,CI R,CI v){RI i,mx=0;for(i=L;i<=R;i++) mx=max(mx,T[i].Q(v));return mx;}
I void O(PA& o,PA v){H(o,v.fi),H(o,v.se);}
I PA E(CI L,CI R){PA o=MP(0,0);RI i;for(i=L;i<=R;i++){auto it=s[i].rbegin();if(it!=s[i].rend()){H(o,*it);++it;if(it!=s[i].rend()) H(o,*it);}}return o;}
I int Q(RI l,RI r){
    PA o=MP(0,0);RI bL=1,bR=1;W(l>=b[bL].size()) l-=b[bL++].size();W(r>=b[bR].size()) r-=b[bR++].size();if(bL==bR) return O(o,G(bL,l,r)),F(bL,l,r,o.se);
    else return O(o,G(bL,l,b[bL].size()-1)),O(o,G(bR,0,r)),O(o,E(bL+1,bR-1)),max(Z(bL+1,bR-1,o.se),max(F(bL,l,b[bL].size()-1,o.se),F(bR,0,r,o.se)));
}
I void C(CI i,CI v){s[i].erase(s[i].find(v)),T[i].K(v);}
I void J(CI i,CI v){s[i].insert(v),T[i].A(v);}
I void U(RI x,CI v){RI i,bL=1,t;W(x>=b[bL].size()) x-=b[bL++].size();t=b[bL][x],C(bL,t);b[bL][x]=v,J(bL,v);}
I void A(RI x,CI v){
    RI i,t,bL=1;W(x>=b[bL].size()) x-=b[bL++].size();b[bL].insert(b[bL].begin()+x,v),J(bL,v);for(i=bL+1;i<=tot;i++) if(b[i-1].size()<=S) break ;
    else t=b[i-1].back(),C(i-1,t),b[i-1].pop_back(),b[i].insert(b[i].begin(),t),J(i,t);if(b[tot].size()>S) ++tot,T[tot].clear();++n;
}
I void K(RI x){RI i,bL=1,t;W(x>=b[bL].size()) x-=b[bL++].size();t=b[bL][x];b[bL].erase(b[bL].begin()+x),C(bL,t);--n;} 
int main(){
//    freopen("I.in","r",stdin);freopen("I.out","w",stdout);
    RI i,x,l,r,p=0;for(read(n,m),tot=n/S+1,i=1;i<=tot;i++) T[i].clear();for(i=0;i<n;i++) read(x),b[i/S+1].push_back(x),s[i/S+1].insert(x),T[i/S+1].A(x);
    W(m--) if((x=RC())==1) read(l,r),l=(l+p)%n,r=(r+p)%P,A(l,r);else if(x==2) read(l),l=(l+p)%n,K(l);
    else if(x==3) read(l,r),l=(l+p)%n,r=(r+p)%P,U(l,r);else if(x==4) read(l,r),l=(l+p)%n,r=(r+p)%n,l>r&&(swap(l,r),0),writeln(p=Q(l,r));return 0;
}