#include<stdio.h>
#include<fstream>
#include<iostream>
using namespace std;

ifstream f("aib.in");
ofstream g("aib.out");

#define MaxN 100100

int N,M,stare,Trie[MaxN];

void Update(int i,int val)
{
	for(;i<=N;)
	{
		Trie[i] += val;
		i += (i & -i);
	}
}

void citire(void)
{
	int a;
	
	f >> N >> M;
	for(int i=1;i<=N;i++)
	{
		f >> a;
		Update(i,a);
	}
}

int Suma(int i)
{
	int val = 0;
	for(;i;)
	{
		val += Trie[i];
		i -= (i & -i);
	}
	
	return val;
}

int Search(int li,int ls,int a)
{
	int c = Suma((li+ls)/2);
	
	if(li <= ls)
	if(c == a)
		return (li+ls)/2;
	else if(c > a)
		return Search(li,(li+ls)/2 - 1,a);
	else
		return Search((li+ls)/2 + 1, ls,a);
	
	return 0;
}

int main()
{
	int a,b;
	
	citire();
	
	for(int i=1;i<=M;i++)
	{
		f >> stare;
		switch(stare)
		{
			case 0 : f >> a >> b; Update(a,b); break;
			case 1 : f >> a >> b; g << Suma(b) - Suma(a-1) << "\n"; break;
			case 2 : f >> a ; a = Search(1,N,a); g << (a ? a : -1) << "\n"; 
		}
	}
	
	return 0;
}