#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <ctime>
using namespace std;
int n, m, a[50005], opt, uu, vv, ww, ans;
const int oo=2147483647;
namespace treap{
struct Node{
int l, r, siz, val, hav, rnd;
}nd[5000005];
int tot;
void upd(int k){
nd[k].siz = nd[nd[k].l].siz + nd[nd[k].r].siz + nd[k].hav;
}
void lRotate(int &k){
int t=nd[k].r; nd[k].r = nd[t].l; nd[t].l = k;
nd[t].siz = nd[k].siz; upd(k); k = t;
}
void rRotate(int &k){
int t=nd[k].l; nd[k].l = nd[t].r; nd[t].r = k;
nd[t].siz = nd[k].siz; upd(k); k = t;
}
void insert(int &k, int x){
if(!k){
k = ++tot; nd[k].siz = nd[k].hav = 1;
nd[k].val = x; nd[k].rnd = rand();
return ;
}
nd[k].siz++;
if(nd[k].val==x) nd[k].hav++;
else if(nd[k].val>x){
insert(nd[k].l, x);
if(nd[nd[k].l].rnd<nd[k].rnd) rRotate(k);
}
else{
insert(nd[k].r, x);
if(nd[nd[k].r].rnd<nd[k].rnd) lRotate(k);
}
}
void shanchu(int &k, int x){
if(!k) return ;
if(nd[k].val==x){
if(nd[k].hav>1){
nd[k].hav--;
nd[k].siz--;
return ;
}
if(nd[k].l*nd[k].r==0) k = nd[k].l + nd[k].r;
else if(nd[nd[k].l].rnd<nd[nd[k].r].rnd) rRotate(k), shanchu(k, x);
else lRotate(k), shanchu(k, x);
}
else if(nd[k].val>x)
nd[k].siz--, shanchu(nd[k].l, x);
else
nd[k].siz--, shanchu(nd[k].r, x);
}
int queryRank(int k, int x){
if(!k) return 0;
if(nd[k].val>x) return queryRank(nd[k].l, x);
else if(nd[k].val<x) return queryRank(nd[k].r, x)+nd[nd[k].l].siz+nd[k].hav;
else return nd[nd[k].l].siz;
}
void queryPre(int k, int x){
if(!k) return ;
if(nd[k].val<x) ans = max(ans, nd[k].val), queryPre(nd[k].r, x);
else queryPre(nd[k].l, x);
}
void queryNxt(int k, int x){
if(!k) return ;
if(nd[k].val>x) ans = min(ans, nd[k].val), queryNxt(nd[k].l, x);
else queryNxt(nd[k].r, x);
}
}
namespace sgt{
int rot[200005];
void insert(int o, int l, int r, int x, int k){
treap::insert(rot[o], k);
if(l==r) ;
else{
int mid=(l+r)>>1;
int lson=o<<1;
int rson=lson|1;
if(x<=mid) insert(lson, l, mid, x, k);
if(mid<x) insert(rson, mid+1, r, x, k);
}
}
void shanchu(int o, int l, int r, int x, int k){
treap::shanchu(rot[o], k);
if(l==r) ;
else{
int mid=(l+r)>>1;
int lson=o<<1;
int rson=lson|1;
if(x<=mid) shanchu(lson, l, mid, x, k);
if(mid<x) shanchu(rson, mid+1, r, x, k);
}
}
int queryRank(int o, int l, int r, int x, int y, int k){
if(l>=x && r<=y) return treap::queryRank(rot[o], k);
else{
int mid=(l+r)>>1;
int lson=o<<1;
int rson=lson|1;
int re=0;
if(x<=mid) re += queryRank(lson, l, mid, x, y, k);
if(mid<y) re += queryRank(rson, mid+1, r, x, y, k);
return re;
}
}
void queryPre(int o, int l, int r, int x, int y, int k){
if(l>=x && r<=y) treap::queryPre(rot[o], k);
else{
int mid=(l+r)>>1;
int lson=o<<1;
int rson=lson|1;
if(x<=mid) queryPre(lson, l, mid, x, y, k);
if(mid<y) queryPre(rson, mid+1, r, x, y, k);
}
}
void queryNxt(int o, int l, int r, int x, int y, int k){
if(l>=x && r<=y) treap::queryNxt(rot[o], k);
else{
int mid=(l+r)>>1;
int lson=o<<1;
int rson=lson|1;
if(x<=mid) queryNxt(lson, l, mid, x, y, k);
if(mid<y) queryNxt(rson, mid+1, r, x, y, k);
}
}
}
int queryNum(int uu, int vv, int ww){
int l=0, r=1e8, mid, re;
while(l<=r){
mid = (l + r) >> 1;
if(sgt::queryRank(1, 1, n, uu, vv, mid)+1<=ww) re = mid, l = mid + 1;
else r = mid - 1;
}
return re;
}
int main(){
srand(time(NULL));
cin>>n>>m;
for(int i=1; i<=n; i++){
scanf("%d", &a[i]);
sgt::insert(1, 1, n, i, a[i]);
}
while(m--){
scanf("%d", &opt);
if(opt==1){
scanf("%d %d %d", &uu, &vv, &ww);
printf("%d
", sgt::queryRank(1, 1, n, uu, vv, ww)+1);
}
if(opt==2){
scanf("%d %d %d", &uu, &vv, &ww);
printf("%d
", queryNum(uu, vv, ww));
}
if(opt==3){
scanf("%d %d", &uu, &vv);
sgt::shanchu(1, 1, n, uu, a[uu]);
a[uu] = vv;
sgt::insert(1, 1, n, uu, a[uu]);
}
if(opt==4){
scanf("%d %d %d", &uu, &vv, &ww);
ans = -oo;
sgt::queryPre(1, 1, n, uu, vv, ww);
printf("%d
", ans);
}
if(opt==5){
scanf("%d %d %d", &uu, &vv, &ww);
ans = oo;
sgt::queryNxt(1, 1, n, uu, vv, ww);
printf("%d
", ans);
}
}
return 0;
}