#include<bits/stdc++.h>

using namespace std;
ifstream fin ("aib.in");
ofstream fout ("aib.out");
int n,i,j,a,b,m,x,c;
int s[100001];
void adun(int x,int y);
int suma(int x);
int cautare(int st,int dr,int x);
int main()
{
	fin>>n>>m;
	for(i=1; i<=n; i++)
	{
		fin>>x;
		adun(i,x);
	}
	for(i=1; i<=m; i++)
	{
		fin>>c>>a;
		if(c<2)
         fin>>b;
        if (c==0)
            adun(a,b);
        else
            if (c==1)
            fout<<suma(b)-suma(a-1)<<'\n';
        else
            fout<<cautare(1,n,a)<<'\n';
	}
	fout.close();
	return 0;
}
void adun(int x,int y)
{
	int k=1;
	while((x&k)==0)
        k<<=1;
	s[x]+=y;
	while(x+k<=n)
	{
		x=x+k;
		s[x]+=y;
		while((x&k)==0)
		k<<=1;
	}
}
int suma(int x)
{
	if(x==0)
    return 0;
	int k=1,sum;
	while((x&k)==0)
	k<<=1;
	sum=s[x];
	while(x-k>0)
	{
		x=x-k;
		sum+=s[x];
		while((x&k)==0)
		k<<=1;
	}
	return sum;
}
int cautare(int st,int dr,int x)
{
	int mij,k;
	while(st<dr)
	{
		mij=(st+dr)/2;
		k=suma(mij);
		if(k==x)
        return mij;
		if(k<x)
			st=mij+1;
		else
			dr=mij-1;
	}
	if(suma(st)==x)
        return st;
	else
		return -1;
}