#include<fstream>
using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");
#define lung 100001
#define numar(x) ((x^(x-1))&x)
int aib[lung],n;
inline void update(int ind,int val)
{int i;
    for (i=ind;i<=n;i+=numar(i))
		aib[i]+=val;
}
inline int aduna(int val)
{int i,sum=0;
    for (i=val;i;i-=numar(i))
		sum+= aib[i];
    return sum;
}
inline int caut_binar(int sum)
{int st=1,dr=n,mid,x;
    while (dr>st)
	{   mid= (st+dr)/2;
        x=aduna(mid);
		if ( x>sum )
			dr=mid-1; 
		else
			if ( x<sum )
				st=mid+1; 
			else 
				return mid;
	}
	return (aduna(st)==sum ) ? st : -1 ;
}

int main()
{int i,aux,x,y,m;
    fin >> n >> m;
    for (i=1;i<=n;++i)
	{	fin >> aux;
	    update(i,aux);
    }
	for (;m;--m)
	{   fin >> aux;
	    switch (aux)
	    {   case 0:
				fin >> x >> y;
				update(x,y);
				break;
	    	case 1:
			    fin >> x >> y;
				y = aduna(y)-aduna(x-1);
				fout << y << '\n';;
				break;
			case 2:
			    fin >> x;
				fout << caut_binar(x) << '\n';
				break;
		}
	}
	return 0;
}