#include<bits/stdc++.h>
#define rep(a, b, c) for(int a=(b);a<=(c);a++)
#define rop(a, b, c) for(int a=(b);a>=(c);a--)
#define pii pair<int,int>
#define mkp make_pair
#define fi first
#define se second
using namespace std;
const int N=5e5+10;
int pos[N], bl[N], br[N];
struct cnode{int x, y;}c[N]; 
struct qnode{int l, r, a, b, t, id;}q[N]; 
inline bool cmp(qnode a, qnode b) {return (pos[a.l]^pos[b.l])?pos[a.l]<pos[b.l]:((pos[a.r]^pos[b.r])?pos[a.r]<pos[b.r]:a.t<b.t);}
int n, m, ti, num, b[N], a[N], ans[N];

void init(int n, int siz) {
	int len=ceil((double)n/siz);
	rep(i, 1, len) {
		bl[i]=siz*(i-1)+1;
		br[i]=siz*i;
		rep(j, bl[i], br[i]) pos[j]=i;
	}
}

struct BK{
	int cnt[N], cb[N][2];
	inline void add(int x) {
		cb[pos[x]][cnt[x]&1]-=(cnt[x]>0);
		cnt[x]++;
		cb[pos[x]][cnt[x]&1]+=(cnt[x]>0);
	}
	inline void del(int x) {
		cb[pos[x]][cnt[x]&1]-=(cnt[x]>0); 
		cnt[x]--;
		cb[pos[x]][cnt[x]&1]+=(cnt[x]>0);
	}
	inline int qry(int l, int r) {
//		cerr<<"#:"<<l<<' '<<r<<' '<<pos[l]<<' '<<pos[r]<<'\n';
//		rep(i, 1, n) cerr<<i<<' '<<cnt[i]<<' '<<pos[i]<<'\n';
//		if(l==1&&r==5) {
//			cerr<<"begin: \n"; 
//			rep(i, 1, n) cerr<<i<<' '<<cnt[i]<<' '<<pos[i]<<'\n';
//			cerr<<"end.\n";
//		} 
		if(pos[l]==pos[r]) {
			bool v=0;
			rep(i, l, r) {
				if(!cnt[i]) continue;
				if(v) return i;
				v=cnt[i]&1^1;
			} return -1;
		}
		bool v=0;
		rep(i, l, br[pos[l]]) {
			if(!cnt[i]) continue;
			if(v) return i;
			v|=cnt[i]&1^1;
		}
		rep(i, pos[l]+1, pos[r]-1) {
			if(cb[i][0]==0&&cb[i][1]==0) continue;
			if(v||(cb[i][0]>0)) {
				rep(j, bl[i], br[i]) {
					if(!cnt[j]) continue;
					if(v) return j;
					v|=cnt[j]&1^1;
				}
			} v|=(cb[i][0]>0);
		}
		rep(i, bl[pos[r]], r) {
			if(!cnt[i]) continue;
			if(v) return i;
			v|=cnt[i]&1^1;
		} return -1;
	}
}B;

signed main(){
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin>>n>>num;
	rep(i, 1, n) {cin>>a[i]; b[i]=a[i];}
	rep(i, 1, num) {
		int opt; 
		cin>>opt;
		if(opt==1) {
			ti++;
			cin>>c[ti].x>>c[ti].y;
			c[ti].y=(b[c[ti].x]+=c[ti].y);
//			cout<<ti<<'\n';
		} else {
			m++;
			cin>>q[m].l>>q[m].r>>q[m].a>>q[m].b;
			q[m].t=ti; q[m].id=m;
//			cout<<ti<<'\n';
		}
	}
	init(n, pow(n, 2.0/3.0));
	sort(q+1, q+m+1, cmp);
	init(n, sqrt(n));
	int l=1, r=0, t=0;
	rep(i, 1, m) {
		int ql=q[i].l, qr=q[i].r, qt=q[i].t, qid=q[i].id, qa=q[i].a, qb=q[i].b;
		while(l>ql) B.add(a[--l]);
		while(r<qr) B.add(a[++r]);
		while(l<ql) B.del(a[l++]);
		while(r>qr) B.del(a[r--]);
//		cout<<qid<<' '<<t<<' '<<qt<<'\n';
		while(t<qt) {
			++t;
			if(ql<=c[t].x&&c[t].x<=qr) B.del(a[c[t].x]), B.add(c[t].y);
			swap(a[c[t].x], c[t].y);
		}
		while(t>qt) {
			if(ql<=c[t].x&&c[t].x<=qr) B.del(a[c[t].x]), B.add(c[t].y);
			swap(a[c[t].x], c[t].y);
			t--;
		}
		ans[qid]=B.qry(qa, qb); 
	}
	rep(i, 1, m) cout<<ans[i]<<'\n';
	return 0;
}