#include <cstdlib>
#include <cstdio>
#include <iostream>

#define maxn 100001
#define maxm 150001

using namespace std;

int arb[maxn];

int sum(int value)
{
	int s = 0, x, nr;
	while (value > 0) {
		x = value;
		s += arb[value];
 		nr = 1;
		while ((x & 1) == 0) {
			nr = nr << 1;
			x = x >> 1; 
		}
		value -= nr;
	}
	return s;
}

int bsearch(int low, int high, int value)
{
	int m = (low + high) / 2;
	int s = sum(m);
	if (s == value)
	       return m; 
	if (low >= high) {
		return -1;
	} 
	if (s < value)
		return bsearch(m + 1, high, value);
	else
		return bsearch(low, m, value);
}

void update(int poz, int val, int n)
{
	int C = 0;
	while (poz <= n)
	{
		arb[poz] += val;
		while ( !(poz & (1<<C)) ) C++;
		poz += (1<<C);
		C += 1;
	}
}


int main()
{
	int n, m, i, cod, s, value1, value2;
	FILE *f = fopen("aib.in", "rt");
	FILE *g = fopen("aib.out", "wt");
	fscanf(f, "%d" , &n);
	fscanf(f, "%d" , &m);
	for (i = 0; i < n; i++) {
		fscanf(f, "%d" , &value1);
		update(i + 1, value1, n);
	}
	for (i = 0; i < m; i++) {
		fscanf (f, "%d" , &cod);
		if (cod == 0) {
			fscanf(f, "%d" , &value1);
			fscanf(f, "%d" , &value2);
			update(value1, value2, n); 
		}
		if (cod == 1) {
			fscanf(f, "%d" , &value1);
			fscanf(f, "%d" , &value2);
			s = sum(value2) - sum(value1 - 1);
			fprintf(g, "%d\n" , s);
		}
		if (cod == 2) {
			fscanf (f, "%d" , &value1);
			fprintf(g, "%d\n",  bsearch(1, n, value1));
		}
	}  
	fclose(f);
	fclose(g);
	return 0;
}