#include<stdio.h>
#define dim 100001
#define zero(poz) ((poz^(poz-1))&poz)
using namespace std;

int a[dim], n, x, poz, val;

void update(int poz, int val)
{ 
	while(poz <= n) 
		{ a[poz] += val;
		  poz += zero(poz);
		}
}

int query(int poz)
{ int s = 0;
	
	while(poz > 0)
		{ s += a[poz];
		  poz -= zero(poz);
		}
	return s;
}


int cautare(int x)
{ int dr, st, mij, k;
	
	st = 1; dr = n;
	
	while(st <= dr)
		{
			mij = (st + dr)>>1;
			k = query(mij);
	
			if(k == x)
				return mij;
			  else if(k > x) dr = mij - 1;
				  else st = mij + 1;
		}
	return -1;
}


int main()
{ int nr, i, y, m;

	FILE *f = fopen("aib.in", "r");
	FILE *g = fopen("aib.out", "w");
	
	fscanf(f, "%d%d", &n, &m);
	
	for(i = 1; i <= n; i++)
		{fscanf(f, "%d", &x);
		 update(i, x);
		}
		
	for( i = 1; i <= m; i++ )
		{
			fscanf(f, "%d%d", &nr, &x);
			
			if(!nr) 
				{	fscanf(f, "%d", &y);
					update(x, y);
				}
			  else if(nr == 1) 
				        {	fscanf(f, "%d", &y);
							fprintf(g, "%d\n", query(y) - query(x-1));
					    }
				else fprintf(g, "%d\n", cautare(x));
		}
		
	
	
	
	fclose(f);
	fclose(g);
	return 0;
}