#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 5e5 + 5, inf = 1e9 + 5;
vector<int> clearpos;
struct tree{
#define mid ((l + r) >> 1)
#define ls (now << 1)
#define rs (now << 1 | 1)
	int a[(1 << 20) + 5][16], tag[(1 << 20) + 5][16];
	int vecl[(1 << 20) + 5][16], vecr[(1 << 20) + 5][16];
	void up(int now, int k){
		if (k >= 8) return;
		int &mx = a[now][k << 1], &mx2 = a[now][k << 1 | 1];
		int &lmx = vecl[now][k << 1] = 0, &rmx = vecr[now][k << 1] = 0;
		int &lmx2 = vecl[now][k << 1 | 1] = 0, &rmx2 = vecr[now][k << 1 | 1] = 0;
		mx = mx2 = -inf;
		for (int x = vecl[now][k]; x; x ^= x & -x)
			mx = max(a[ls][__builtin_ctz(x) << 1], mx);
		for (int x = vecr[now][k]; x; x ^= x & -x)
			mx = max(a[rs][__builtin_ctz(x) << 1], mx);
		for (int x = vecl[now][k]; x; x ^= x & -x){
			int _kl = __builtin_ctz(x);
			mx2 = max(a[ls][_kl << 1 | (a[ls][_kl << 1] == mx)], mx2);
			if (a[ls][_kl << 1] == mx) lmx |= 1 << (_kl << 1);
		}
		for (int x = vecr[now][k]; x; x ^= x & -x){
			int _kr = __builtin_ctz(x);
			mx2 = max(a[rs][_kr << 1 | (a[rs][_kr << 1] == mx)], mx2);
			if (a[rs][_kr << 1] == mx) rmx |= 1 << (_kr << 1);
		}
		for (int x = vecl[now][k]; x; x ^= x & -x)
			lmx2 |= (2 | (a[ls][__builtin_ctz(x) << 1] != mx)) << (__builtin_ctz(x) << 1);
		for (int x = vecr[now][k]; x; x ^= x & -x)
			rmx2 |= (2 | (a[rs][__builtin_ctz(x) << 1] != mx)) << (__builtin_ctz(x) << 1);
		up(now, k << 1);
		up(now, k << 1 | 1);
	}
	void update(int now, int k, int _k){
		a[now][k] += _k;
		tag[now][k] += _k;
	}
	void down(int now){
		for (int k = 1; k < 16; k++)
			if (tag[now][k]){
				for (int x = vecl[now][k]; x; x ^= x & -x)
					update(ls, __builtin_ctz(x), tag[now][k]);
				for (int x = vecr[now][k]; x; x ^= x & -x)
					update(rs, __builtin_ctz(x), tag[now][k]);
				tag[now][k] = 0;
			}
	}
	void clear(int now){
		memset(a[now], -0x3f, sizeof(a[now]));
	}
	void build(int now, int l, int r){
		clear(now);
		if (l == r) return;
		vecl[now][1] = vecr[now][1] = 2;
		build(ls, l, mid);
		build(rs, mid + 1, r);
	}
	void clear(int now, int l, int r, int k){
		if (a[now][k] < 0) return;
		if (l == r){
			clearpos.push_back(l);
			return;
		}
		down(now);
		for (int x = vecl[now][k]; x; x ^= x & -x)
			clear(ls, l, mid, __builtin_ctz(x));
		for (int x = vecr[now][k]; x; x ^= x & -x)
			clear(rs, mid + 1, r, __builtin_ctz(x));
	}
	void add(int now, int l, int r, int k, int x){
		if (k >= 8){
			clear(now, l, r, k);
			return;
		}
		if (a[now][k << 1] < 0) return;
		int mx1 = a[now][k << 1], mx2 = a[now][k << 1 | 1];
		if (x > mx1){
			add(now, l, r, k << 1, x);
			if (mx2 > 0) add(now, l, r, k << 1 | 1, x);
		}else if (x > mx2){
			update(now, k << 1, x - mx1);
			if (mx2 > 0) add(now, l, r, k << 1 | 1, x);
		}else{
			if (l == r){
				a[now][k << 1] = x;
				int y = k << 1 | 1;
				for (int i = 0; (y << i) < 16; i++)
					for (int j = 0; j < (1 << i); j++)
						a[now][(y << i) | j] = -inf;
				return;
			}
			down(now);
			for (int _x = vecl[now][k]; _x; _x ^= _x & -_x)
				add(ls, l, mid, __builtin_ctz(_x), x);
			for (int _x = vecr[now][k]; _x; _x ^= _x & -_x)
				add(rs, mid + 1, r, __builtin_ctz(_x), x);
			up(now, k);
		}
	}
	void add(int now, int l, int r, int s, int t, int x){
		if (s <= l && r <= t) return add(now, l, r, 1, x);
		down(now);
		if (s <= mid) add(ls, l, mid, s, t, x);
		if (t > mid) add(rs, mid + 1, r, s, t, x);
		up(now, 1);
	}
	void set(int now, int l, int r, int s){
		for (int i = 1; i < 16; i++) a[now][i] = inf + (i ^ 1);
		if (l == r) return;
		down(now);
		if (s <= mid) set(ls, l, mid, s);
		else set(rs, mid + 1, r, s);
	}
	void set2(int now, int l, int r, int s){
		if (l == r){
			clear(now);
			return;
		}
		down(now);
		if (s <= mid) set2(ls, l, mid, s);
		else set2(rs, mid + 1, r, s);
		up(now, 1);
	}
#undef mid
#undef ls
#undef rs
}T;
int n, m, tot;
int stt[N], ans[N];
vector<pair<int, int>> vec[N];
vector<int> ad[N];
char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf,*O2=obuf+(1<<23);
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int read() {
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
	return x*f;
}
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
//	freopen("ds.in", "r", stdin);
//	freopen("ds.out", "w", stdout);
	n = read(), m = read();
	for (int i = 1; i <= n; i++){
		int x = read();
		vec[i].emplace_back(1, x);
	}
	for (int i = 1; i <= m; i++){
		int opt = read();
		if (opt == 1){
			int j = read(), y = read();
			vec[j].emplace_back(tot + 1, y);
		}else{
			tot++;
			stt[tot] = read();
			ans[tot] = -1;
			ad[stt[tot]].push_back(tot);
		}
	}
	T.build(1, 1, tot);
	for (int i = 1; i <= n; i++){
		for (int x : ad[i]) T.set(1, 1, tot, x);
		for (int j = 0; j < (int)vec[i].size(); j++){
			int l = vec[i][j].first, r = j + 1 == (int)vec[i].size() ? tot : vec[i][j + 1].first - 1;
			if (l <= r) T.add(1, 1, tot, l, r, vec[i][j].second);
			for (int x : clearpos){
				ans[x] = i;
				T.set2(1, 1, tot, x);
			}
			clearpos.clear();
		}
	}
	for (int i = 1; i <= tot; i++) cout << ans[i] << endl;
	return 0;
}

In file included from /usr/include/c++/13/string:43,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from answer.code:3:
/usr/include/c++/13/bits/allocator.h: In destructor ‘std::_Vector_base<int, std::allocator<int> >::_Vector_impl::~_Vector_impl()’:
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = int]’: target specific option mismatch
  184 |       ~allocator() _GLIBCXX_NOTHROW { }
      |       ^
In file included from /usr/include/c++/13/vector:66,
                 from /usr/include/c++/13/queue:63,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:157:
/usr/include/c++/13/bits/stl_vector.h:133:14: note: called from here
  133 |       struct _Vector_impl
      |              ^~~~~~~~~~~~