Problem: Given n numbers a0, a1, ..., an-1 and q.
I want you to perform appropriate processing for q queries.
The query has the following three types of operations.


* Shift the value
Given a pair of l and r. (l <r) Circular shift the value from al to ar.

0 1 2 3 4 5 6 7 8 9

Is given the query l = 2, r = 5.

The shifted number sequence is

0 1 5 2 3 4 6 7 8 9

Will be.


* Find the minimum value
Given a pair of l and r. (l ≤ r)
Find the smallest value from al to ar.


* Update value
Given a pair of pos and val. Update the value of apos to val.



Input

The input is given in the following format.


n q
a0
a1
..
..
..
an-1
x1 y1 z1
x2 y2 z2
..
..
..
xq yq zq


If xi = 0, it represents a shift query. At this time, let l = yi and r = zi.
If xi = 1, it represents a query for the minimum value. At this time, let l = yi and r = zi.
If xi = 2, it represents a query that updates the value. At this time, pos = yi, val = zi.


Input meets the following constraints
1 ≤ n, q ≤ 200,000
0 ≤ ai ≤ 10,000,000 For queries that update values, 0 ≤ val ≤ 10,000,000

Output

When xi = 1 is given as a query, output the value of the answer on one line.

Examples

Input

10 3
0
1
2
3
4
5
6
7
8
9
1 5 7
0 2 5
1 5 7


Output

5
4


Input

10 10
289383
930886
692777
636915
747793
238335
885386
760492
516649
641421
2 7 368690
1 3 6
0 2 6
1 1 8
0 2 9
2 2 665123
1 5 9
0 2 8
2 7 961393
1 1 2


Output

238335
238335
238335
368690

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;

#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define mp(a,b) make_pair((a),(b))
#define debug(x) #x << "=" << (x)
 
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define dump(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define dump(x)
#endif

typedef long long int ll;
typedef pair<int,int> pii;
//template<typename T> using vec=std::vector<T>;

const int inf=1<<30;
const long long int inf64=1LL<<58;
const double EPS=1e-9;
const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
	os << "[";
	for (const auto &v : vec) {
		os << v << ",";
	}
	os << "]";
	return os;
}

class xor128{
public:
	static int rand(){
		t=x^(x<<11);
		x=y;
		y=z;
		z=w;
		w=(w^(w>>19))^(t^(t>>8));
		return w & 0x7fffffff;
	}
	private:
	static unsigned int x;
	static unsigned int y;
	static unsigned int z;
	static unsigned int w;
	static unsigned int t;
};
unsigned int xor128::x=123456789;
unsigned int xor128::y=362436069;
unsigned int xor128::z=521288629;
unsigned int xor128::w=88675123;
unsigned int xor128::t=1;

template<class T> class rbst{
public:
	struct node{
		T val,min;
		node* left,*right;
		unsigned sz;
		node(T val):val(val),min(val),left(NULL),right(NULL),sz(1){}
	};

	node* root;
	rbst():root(NULL){}

	unsigned size(){ return size(root); }
	unsigned size(node*v){ return v?v->sz:0; }
	T min(node* v){ return v?v->min:numeric_limits<T>::max(); }

	node* update(node* x){
		x->sz=size(x->left)+size(x->right)+1;
		x->min=std::min({x->val,min(x->left),min(x->right)});
		return x;
	}

	node* merge(node* x,node* y){
		if(!x or !y) return x?x:y;
		
		int m=x->sz,n=y->sz;
		if(xor128::rand()%(m+n)<m){
			x->right=merge(x->right,y);
			return update(x);
		}
		y->left=merge(x,y->left);
		return update(y);
	}

	//[0,pos),[pos,sz)
	pair<node*,node*> split(node *v,unsigned pos){
		if(!v) return pair<node*,node*>(NULL,NULL);
		if(pos<=size(v->left)){
			pair<node*,node*> s=split(v->left,pos);
			v->left=s.second;
			return make_pair(s.first,update(v));
		}
		auto s=split(v->right,pos-size(v->left)-1);
		v->right=s.first;
		return make_pair(update(v),s.second);
	}
	

	node* insert(unsigned pos,T val){ return root=insert(root,pos,val); }
	node* insert(node* x,int pos,T val){
		auto y=split(x,pos);
		x=merge(y.first,new node(val));
		x=merge(x,y.second);
		return update(x);
	}

	node* erase(int pos){ return root=erase(root,pos); }
	node* erase(node* x,int pos){
		auto tmp1=split(x,pos-1);
		node* l=tmp1.first;
		auto tmp2=split(tmp1.second,1);
		node* r=tmp2.second;
		delete tmp2.first;
		return merge(l,r);
	}

	node* at(unsigned pos){
		node* x=root;
		while(x){
			unsigned sz=size(x->left);
			if(sz>pos) x=x->left;
			else if(sz==pos) return x;
			else{
				x=x->right;
				pos-=sz+1;
			}
		}
		return x;
	}

	//[l,r)
	node* rotate(int l,int r){
		auto u=split(root,r),v=split(u.first,r-1),w=split(v.first,l);
		return root=merge(merge(w.first,v.second),merge(w.second,u.second));
	}

	//[l,r)
	T min(int l,int r){
		auto u=split(root,r),v=split(u.first,l);
		auto res=min(v.second);
		root=merge(merge(v.first,v.second),u.second);
		return res;
	}

	node* update(int pos,T val){
		auto u=split(root,pos+1),v=split(u.first,pos);
		v.second->val=val;
		update(v.second);
		return root=merge(merge(v.first,v.second),u.second);
	}
};

void solve(){
    int n,q;
    cin >> n >> q;
    
    rbst<int> t;
    rep(i,0,n){
        int a;
        cin >> a;
        t.insert(i,a);
    }
    t.min(5,8);
    rep(i,0,q){
        int x,y,z;
        cin >> x >> y >> z;
        if(x==0) t.rotate(y,z+1);
        else if(x==1) cout << t.min(y,z+1) << endl;
        else t.update(y,z);
    }
}

int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	solve();
	return 0;
}