#include <fstream>
#include <iostream>
using namespace std;
int v[100005], n;
void add(int x, int a) {
	int i, poz;
	poz = x;
	i = 0;
	while ( poz < n ) {
		if (x % 2 == 0) {
			v[poz] += a;
			poz += ( 1 << i );
		}
		x /= 2;
		i++;
	}
}
int sum(int x) {
	int i, poz, s;
	i = s = 0;
	poz = x - 1;
	while (x > 0) {
		if (x % 2 == 1) {
			s += v[poz];
			poz -= ( 1 << i );
		}
		x /= 2;
		i++;
	}
	return s;
}
int main() {
	int m, i, j, x, tip, a, b, stanga, dreapta, mijloc;
	ifstream fin( "aib.in" );
	ofstream fout( "aib.out" );
	fin >> n >> m;
	for (i = 0; i < n; i++) {
		fin >> x;
		add( i, x );
	}
	/*for (i = 0; i < n; i++) {
		cout << v[i] << ' ';
	}*/
	for (i = 0; i < m; i++) {
		fin >> tip >> a;
		if (tip == 0) {
			fin >> b;
			add( a - 1, b );
		}
		else if (tip == 1) {
			fin >> b;
			fout << sum( b ) - sum( a - 1 ) << '\n';
		}
		else {
			stanga = 0;
			dreapta = n;
			while (dreapta - stanga > 1) {
				mijloc = ( stanga + dreapta ) / 2;
				if (sum(mijloc) < a) {
					stanga = mijloc;
				}
				else {
					dreapta = mijloc;
				}
			}
			if (sum(dreapta) != a) {
				dreapta = -1;
			}
			fout << dreapta << '\n';
		}
	}
	return 0;
}