#include <cstdio>
#include <cstring>
#include <algorithm>
#define infile "aib.in"
#define outfile "aib.out"
#define n_max 100005
#define zeros(x) (x&(x-1))^x
using namespace std;

int N, M;

int AIB[n_max];



void add(int poz, int val)
{
	for(int i=poz; i<=N; i += zeros(i))
		AIB[i] += val;
}


int sum(int poz)
{
	int rez = 0;
	for(int i = poz; i; i -= zeros(i))
		rez += AIB[i];
	
	return rez;
}


int min_k (int val)
{
	int step;
	
	for(step = 1; step < N;  step <<= 1);

    for(int i = 0; step; step >>= 1)
		if(i + step <= N)
			if(val >= AIB[ i + step])
			{
				i += step;
				val -= AIB[i];
				
				if(!val)
					return i;
			}	
	return -1;
}


int main(void)
{
    freopen(infile, "r", stdin);
	freopen(outfile, "w", stdout);
    
	int op, x, y;
	
	scanf("%d %d", &N, &M);
	
	for(int i=1;i<=N; ++i)
	{
		scanf("%d",&x);
		add(i,x);
	}
	
	while(M--)
	{
		scanf("%d %d",&op, &x);
		
		if(op <= 1)
			scanf("%d",&y);
		
		switch(op)
		{
		case 0: add(x,y);                          break;
	    case 1: printf("%d\n", sum(y) - sum(x-1)); break;
	    case 2: printf("%d\n", min_k(x));          break;
		}
	}

    fclose(stdin);
	fclose(stdout);
    
    return 0;
}