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

#define maxn 100000
#define maxm 150000

using namespace std;

int v[maxn];
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);
}	

int main()
{
	int n, m, i, cod, s, value1, value2, j, x, poz, nr;
	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" , &v[i]);
	}
	for (i = 0; i < n; i++) {
		x = i + 1;
		nr = 1;
		while ((~x) & 1) {
			nr = nr << 1;
			x = x >> 1;
		}
		poz = i + 1;
		for (j = 0; j < nr; j++) {
			arb[i+1] += v[--poz];
		}
	}
	for (i = 0; i < m; i++) {
		fscanf (f, "%d" , &cod);
		if (cod == 0) {
			fscanf(f, "%d" , &value1);
			fscanf(f, "%d" , &value2);
			while (value1 <= n) {
				arb[value1] += value2;
				x = value1;
				nr = 1;
				while ((x & 1) == 0) {
					nr++;
					x = x >> 1; 
				}
				value1 += nr;
			}
		}
		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;
}