#include <bits/stdc++.h>

#define x first
#define y second
#define VM 100005
#define pb push_back
#define ppb pop_back
#define ll long long
#define pii pair<int, int>

using namespace std;

//don't forget to put input in the file!!!
ifstream fin("aib.in");
ofstream fout("aib.out");

int n, m, a[VM], aib[VM];

int lsb(int i){
	return i - (i & (i-1));
}

int query(int p){
	int s=0;
	for(int i=p; i>=1; i-=lsb(i))
		s += aib[i];
	return s;
}

void update(int p, int x){
	for(int i=p; i<=n; i+=i&(-i)){
		aib[i] += x;
	}
	a[p] += x;
}

int search(int a){
	int lo = 1, hi = n, m, s;
	while(lo <= hi){
		m = (lo + hi) / 2;
		s = query(m);
		if(s == a) return m;
		if(s < a) return m + 1;
		if(s > a) return m - 1;
	}
	return -1;
}

int main(){
	fin>>n>>m;
	for(int a, i=1; i<=n; ++i){
		fin>>a;
		update(i, a);
	}

	for(int i=1; i<=m; ++i){
		int op, a, b, c;
		fin>>op;
		if(op == 0){
			fin>>b>>c;
			update(b, c);
			continue;
		}
		if(op == 1){
			fin>>b>>c;
			fout<<query(c) - query(b - 1)<<'\n';
			continue;
		}
		if(op == 2){
			fin>>a;
			fout<<search(a)<<'\n';
			continue;
		}
	}
	
	return 0;
}