记录编号	266692	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015]聪聪的世界	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	35.456 s
提交时间	2016-06-09 09:19:07	内存使用	4.12 MiB

#define maxn 1000001ul

#define fastcall __attribute__((optimize("-O2")))
#define IL __inline__ __attribute__((always_inline))

#define null NULL

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>

struct node{
	long long val,mn,mx,tag; int fix,siz; node *L,*R;
	node(int Val){ fix=rand(),siz=1,val=mn=mx=Val,L=R=null,tag=0; return; }
	fastcall IL int lsize(){ return L!=null?L->siz:0; }
	fastcall IL long long rmin(){return R!=null?R->mn:0x7fffffffffffffffll;}
	fastcall IL long long rmax(){return R!=null?R->mx:-0x7fffffffffffffffll;}
	fastcall IL long long lmin(){return L!=null?L->mn:0x7fffffffffffffffll;}
	fastcall IL long long lmax(){return L!=null?L->mx:-0x7fffffffffffffffll;}
	fastcall IL void upd(){
		mn=mx=val,siz=1;
		if(L!=null){
			siz+=L->siz;
			if(L->mn<mn) mn=L->mn;
			if(L->mx>mx) mx=L->mx;
		}
		if(R!=null){
			siz+=R->siz;
			if(R->mn<mn) mn=R->mn;
			if(R->mx>mx) mx=R->mx;
		} return;
	}
	fastcall IL void pushdown(){
		if(tag){
			if(L!=null) L->givetag(tag);
			if(R!=null) R->givetag(tag);
			tag=0;
		} return;
	}
	fastcall IL void givetag(long long mark){
		val+=mark,mn+=mark,mx+=mark,tag+=mark; return;
	}
}*root;

struct pii{node *x,*y;}A,B,C,D;

int n,m,seq[maxn];

fastcall IL void read(int &x){
	x=0; int c=getchar(); for(;c<'0'||c>'9';c=getchar());
	for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48); return;
}

fastcall void build(node *&rt,int l,int r){
	if(l>r) return;
	int mid=(l+r)>>1; rt=new node(seq[mid]);
	build(rt->L,l,mid-1),build(rt->R,mid+1,r); rt->upd(); return;
}

fastcall node* merge(node *a,node *b){
	if(a==null) return b; if(b==null) return a;
	if(a->fix<b->fix){ a->pushdown(),a->R=merge(a->R,b),a->upd(); return a;}
	else{ b->pushdown(),b->L=merge(a,b->L),b->upd(); return b; }
}

fastcall pii split(node *x,int k){
	if(!k) return (pii){null,x};
	if(x==null||x->siz==k) return (pii){x,null};
	int p=x->lsize(); pii ret; x->pushdown();
	if(p>=k) ret=split(x->L,k),x->L=ret.y,x->upd(),ret.y=x;
	else ret=split(x->R,k-p-1),x->R=ret.x,x->upd(),ret.x=x;
	return ret;
}

fastcall long long find1(node *rt,long long v){
	if(rt==null||rt->mn>=v) return -1;
	rt->pushdown();
	if(rt->rmin()<v) return find1(rt->R,v);
	if(rt->val<v) return rt->val;
	return find1(rt->L,v);
}

fastcall long long find2(node *rt,long long v){
	if(rt==null||rt->mx<=v) return -1;
	rt->pushdown();
	if(rt->rmax()>v) return find2(rt->R,v);
	if(rt->val>v) return rt->val;
	return find2(rt->L,v);
}

fastcall long long find3(node *rt,long long v){
	if(rt==null||rt->mn>=v) return -1;
	rt->pushdown();
	if(rt->lmin()<v) return find3(rt->L,v);
	if(rt->val<v) return rt->val;
	return find3(rt->R,v);
}

fastcall long long find4(node *rt,long long v){
	if(rt==null||rt->mx<=v) return -1;
	rt->pushdown();
	if(rt->lmax()>v) return find4(rt->L,v);
	if(rt->val>v) return rt->val;
	return find4(rt->R,v);
}

fastcall long long get(node *rt,int k){
	rt->pushdown();
	int p=rt->lsize();
	if(p+1==k) return rt->val;
	if(p>=k) return get(rt->L,k);
	return get(rt->R,k-p-1);
}

fastcall void change(node *rt,int k,long long nv){
	rt->pushdown();
	int p=rt->lsize();
	if(p+1==k) rt->val=nv;
	else if(p>=k) change(rt->L,k,nv);
	else change(rt->R,k-p-1,nv); rt->upd(); return;
}

int main(){
	freopen("ccsworld.in","r",stdin);
	freopen("ccsworld.out","w",stdout);
	read(n),read(m);
	for(int i=1;i<=n;i++) read(seq[i]);
	build(root,1,n); long long k,k1,k2;
	for(int i=1,x,y,w,op;i<=m;i++){
		read(op);
		if(op==1){
			read(x),k=get(root,x);
			A=split(root,x-1);
			printf("%lld\n",find1(A.x,k));
			root=merge(A.x,A.y);
		} else if(op==2){
			read(x),k=get(root,x);
			A=split(root,x-1);
			printf("%lld\n",find2(A.x,k));
			root=merge(A.x,A.y);
		} else if(op==3){
			read(x),k=get(root,x);
			A=split(root,x);
			printf("%lld\n",find3(A.y,k));
			root=merge(A.x,A.y);
		} else if(op==4){
			read(x),k=get(root,x);
			A=split(root,x);
			printf("%lld\n",find4(A.y,k));
			root=merge(A.x,A.y);
		} else if(op==5){
			read(x),read(y);
			if(x==y) continue;
			k1=get(root,x),k2=get(root,y);
			change(root,x,k2),change(root,y,k1);
		} else if(op==6){
			read(x),read(y),read(w);
			A=split(root,x-1),B=split(A.y,y-x+1);
			B.x->givetag(w),A.y=merge(B.x,B.y),root=merge(A.x,A.y);
		} else if(op==7){
			read(x),read(y),read(w);
			A=split(root,x-1),B=split(A.y,y-x+1);
			B.x->givetag(-w),A.y=merge(B.x,B.y),root=merge(A.x,A.y);
		}
	} return 0;
}