#include <fstream>
using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");
char buff[4096];
int pbuf=4095;
void readbuff()
{
    pbuf=0;
    fin.read(buff,4095);
}
long long citire()
{
    long long nr=0;
    if(pbuf==4095)
    {
        readbuff();
    }
    while(buff[pbuf]<'0'||buff[pbuf]>'9')
    {
        pbuf++;
        if(pbuf==4095)
        {
            readbuff();
        }
    }
    while(buff[pbuf]>='0'&&buff[pbuf]<='9')
    {
        nr=nr*10+buff[pbuf]-'0';
        pbuf++;
        if(pbuf==4095)
        {
            readbuff();
        }
    }
    return nr;
}
long long aib[100005],cnt;
int n;
void update(int poz,int val)
{
    while(poz<=n)
    {
        aib[poz]+=val;
        poz+=poz&-poz;
    }
}
long long query(int poz)
{
    cnt=0;
    while(poz>0)
    {
        cnt+=aib[poz];
        poz-=poz&-poz;
    }
    return cnt;
}
int main()
{
    long long a,x,y,c1,c2;
    int st,dr,mij,val,poz=1;
    int tip,m;
    n=citire();m=citire();
    for(int i=1;i<=n;i++)
    {
        a=citire();
        update(i,a);
    }
    for(int i=1;i<=m;i++)
    {
        tip=citire();
        if(tip==0)
        {
            x=citire();y=citire();
            update(x,y);
        }
        else if(tip==1)
        {
            x=citire();y=citire();
            c1=query(x-1);c2=query(y);
            fout<<c2-c1<<'\n';
        }
        else if(tip==2)
        {
            x=citire();
            st=1;dr=n;val=-1;c2=0;
            while(dr>=st)
            {
                mij=(st+dr)/2;
                c1=query(mij);
                if(c1>=x)
                {
                    c2=c1;
                    val=mij;
                    dr=mij-1;
                }
                else
                {
                    st=mij+1;
                }
            }
            if(val!=-1)
            {
                if(c2!=x)
                {
                    val=-1;
                }
            }
            fout<<val<<'\n';
        }
    }
    return 0;
}