#include<fstream>
using namespace std;
ifstream in("aib.in");
ofstream out("aib.out");

const int nmax = 100006;
int n, m, v[nmax], aib[nmax], op, a, b;

int zeros(int x)
{
	return (x ^ (x - 1)) & x;
}

void add(int x, int cantitate)
{
	for(int i = x; i<=n; i += zeros(i))
		aib[i] += cantitate;
}

int calc(int x)
{
	int rez = 0;

	for(int i = x; i>0; i -= zeros(i))
		rez += aib[i];

	return rez;
}

int bs(int x)
{
	int lo = 0, hi = n + 1, mid, aux;
	while(hi - lo>1)
	{
		mid = (hi + lo)/2;
		aux = calc(mid);
		
		if(aux==x)
			return mid;
		if(aux<x)
			lo = mid;
		if(aux>x)
			hi = mid;
	}

	if(calc(mid)==x)
		return mid;
	if(calc(hi)==x)
		return hi;
	if(calc(lo)==x)
		return lo;
	return -1;
}

int main(){
	int player_unu=0;

	in>>n>>m;
	for(int i = 1; i<=n; i++)
	{
		in>>v[i];
		add(i, v[i]);
	}

	for(int i = 0; i<m; i++)
	{
		in>>op;

		if(op==0)
		{
			in>>a>>b;
			add(a, b);
		}
		if(op==1)
		{
			in>>a>>b;
			out<<calc(b) - calc(a - 1)<<'\n';
		}
		if(op==2)
		{
			in>>a;
			out<<bs(a)<<'\n';
		}
	}
	return player_unu;
}