#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<algorithm>
#define SIZE(t) ((t)?(t)->size:0)
#define MAXNUM(t) ((t)?(t)->mn:0)
using namespace std;
struct Treap{
Treap *L,*R;
int size,num,mn;
Treap(int _num){
num=mn=_num;
L=R=NULL;
size=1;
}
void up(){
size=SIZE(L)+SIZE(R)+1;
mn=max(num,max(MAXNUM(L),MAXNUM(R)));
}
}*tr;
Treap *merge(Treap *a,Treap *b)
{
if(!a||!b) return a?a:b;
if(rand()%2){
a->R=merge(a->R,b);
a->up();
return a;
}else{
b->L=merge(a,b->L);
b->up();
return b;
}
}
void split(Treap *tr,Treap *&a,Treap *&b,int k)
{
if(k==0){
a=NULL; b=tr;
}else{
if(SIZE(tr->L)>=k){
b=tr;
split(b->L,a,b->L,k);
b->up();
}else{
a=tr;
split(a->R,a->R,b,k-SIZE(a->L)-1);
a->up();
}
}
}
int main()
{
srand(time(NULL));
int n,q;
scanf("%d %d",&n,&q);
int tmp;
scanf("%d",&tmp);
tr=new Treap(tmp);
for(int i=1;i<n;i++){
scanf("%d",&tmp);
tr=merge(tr,new Treap(tmp));
}
for(int i=0;i<q;i++)
{
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
if(a==1)
{
Treap *x,*y,*z;
split(tr,x,y,b-1);
split(y,y,z,1);
y=new Treap(c);
x=merge(x,y);
tr=merge(x,z);
}
else
{
Treap *x,*y,*z;
split(tr,y,z,c);
split(y,x,y,b-1);
printf("%d\n",MAXNUM(y));
x=merge(x,y);
tr=merge(x,z);
}
}
}
I2luY2x1ZGU8Y3N0ZGlvPgojaW5jbHVkZTxjc3RkbGliPgojaW5jbHVkZTxjdGltZT4KI2luY2x1ZGU8YWxnb3JpdGhtPgojZGVmaW5lIFNJWkUodCkgKCh0KT8odCktPnNpemU6MCkgCiNkZWZpbmUgTUFYTlVNKHQpICgodCk/KHQpLT5tbjowKSAKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKc3RydWN0IFRyZWFwewogICAgVHJlYXAgKkwsKlI7CiAgICBpbnQgc2l6ZSxudW0sbW47CiAgICBUcmVhcChpbnQgX251bSl7CiAgICAgICAgbnVtPW1uPV9udW07CiAgICAgICAgTD1SPU5VTEw7IAogICAgICAgIHNpemU9MTsKICAgIH0KICAgIHZvaWQgdXAoKXsKICAgICAgICBzaXplPVNJWkUoTCkrU0laRShSKSsxOwogICAgICAgIG1uPW1heChudW0sbWF4KE1BWE5VTShMKSxNQVhOVU0oUikpKTsKICAgIH0KfSp0cjsKVHJlYXAgKm1lcmdlKFRyZWFwICphLFRyZWFwICpiKQp7CiAgICBpZighYXx8IWIpIHJldHVybiBhP2E6YjsKICAgIGlmKHJhbmQoKSUyKXsKICAgICAgICBhLT5SPW1lcmdlKGEtPlIsYik7CiAgICAgICAgYS0+dXAoKTsKICAgICAgICByZXR1cm4gYTsKICAgIH1lbHNlewogICAgICAgIGItPkw9bWVyZ2UoYSxiLT5MKTsKICAgICAgICBiLT51cCgpOwogICAgICAgIHJldHVybiBiOwogICAgfQp9CnZvaWQgc3BsaXQoVHJlYXAgKnRyLFRyZWFwIComYSxUcmVhcCAqJmIsaW50IGspCnsKICAgIGlmKGs9PTApewogICAgICAgIGE9TlVMTDsgYj10cjsKICAgIH1lbHNlewogICAgICAgIGlmKFNJWkUodHItPkwpPj1rKXsKICAgICAgICAgICAgYj10cjsKICAgICAgICAgICAgc3BsaXQoYi0+TCxhLGItPkwsayk7CiAgICAgICAgICAgIGItPnVwKCk7CiAgICAgICAgfWVsc2V7CiAgICAgICAgICAgIGE9dHI7CiAgICAgICAgICAgIHNwbGl0KGEtPlIsYS0+UixiLGstU0laRShhLT5MKS0xKTsKICAgICAgICAgICAgYS0+dXAoKTsKICAgICAgICB9CiAgICB9Cn0KaW50IG1haW4oKQp7CiAgICBzcmFuZCh0aW1lKE5VTEwpKTsKICAgIGludCBuLHE7CiAgICBzY2FuZigiJWQgJWQiLCZuLCZxKTsKICAgIGludCB0bXA7CiAgICBzY2FuZigiJWQiLCZ0bXApOwogICAgdHI9bmV3IFRyZWFwKHRtcCk7CiAgICBmb3IoaW50IGk9MTtpPG47aSsrKXsKICAgICAgICBzY2FuZigiJWQiLCZ0bXApOwogICAgICAgIHRyPW1lcmdlKHRyLG5ldyBUcmVhcCh0bXApKTsKICAgIH0KICAgICAKICAgIGZvcihpbnQgaT0wO2k8cTtpKyspCiAgICB7CiAgICAgICAgaW50IGEsYixjOwogICAgICAgIHNjYW5mKCIlZCAlZCAlZCIsJmEsJmIsJmMpOwogICAgICAgIGlmKGE9PTEpCiAgICAgICAgewogICAgICAgICAgICBUcmVhcCAqeCwqeSwqejsKICAgICAgICAgICAgc3BsaXQodHIseCx5LGItMSk7CiAgICAgICAgICAgIHNwbGl0KHkseSx6LDEpOwogICAgICAgICAgICB5PW5ldyBUcmVhcChjKTsKICAgICAgICAgICAgeD1tZXJnZSh4LHkpOwogICAgICAgICAgICB0cj1tZXJnZSh4LHopOwogICAgICAgIH0KICAgICAgICBlbHNlCiAgICAgICAgewogICAgICAgICAgICBUcmVhcCAqeCwqeSwqejsKICAgICAgICAgICAgc3BsaXQodHIseSx6LGMpOwogICAgICAgICAgICBzcGxpdCh5LHgseSxiLTEpOwogICAgICAgICAgICBwcmludGYoIiVkXG4iLE1BWE5VTSh5KSk7CiAgICAgICAgICAgIHg9bWVyZ2UoeCx5KTsKICAgICAgICAgICAgdHI9bWVyZ2UoeCx6KTsKICAgICAgICB9CiAgICB9Cn0=