#include<fstream>
using namespace std;

ifstream fin("aib.in");
ofstream fout("aib.out");

int aib[100001], n, m, i, opt, a, b;

inline int nr_de_0(int x) {
	int nr = 0;
	while(x % 2 == 0) {
		x >>= 1;
		nr++;
	}
	return nr;
}

inline int pow_doi(int exp) {
	int rez = 1, i;
	for(i = 1; i <= exp; i++) {
		rez <<= 1;
	}
	return rez;
}

void add(int poz, int val) {
	do {
		aib[poz] += val;
		poz += pow_doi(nr_de_0(poz));
	} while(poz <= n);
}

int suma(int end) {
	int sum = 0;
	do {
		sum += aib[end];
		end -= pow_doi(nr_de_0(end));
	} while(end >= 1);
	return sum;
}

int poz_min(int S) {
	int sum = 0, nr = 1, poz, ans = -1;

	while(nr <= n) nr <<= 1;
	nr >>= 1;

	poz = nr;
	while(nr > 0) {
		nr >>= 1;
		if(sum + aib[poz] <= S) {
			if(poz + nr <= n) {
				ans = poz;
				sum += aib[poz];
				poz += nr;
			}
		} else {
			poz -= nr;
		}
	}
	if(sum == S) return ans;
	return -1;
}

int main() {
	fin >> n >> m;
	for(i = 1; i <= n; i++) {
		fin >> a;
		add(i, a);
	}
	for(i = 0; i < m; i++) {
		fin >> opt;
		if(opt == 0) {
			fin >> a >> b;
			add(a, b);
		}
		if(opt == 1) {
			fin >> a >> b;
			if(a == 1) fout << suma(b) << "\n";
			else fout << suma(b) - suma(a-1) << "\n";
		}
		if(opt == 2) {
			fin >> a;
			fout << poz_min(a) << "\n";
		}
	}
	return 0;
}