#include<cstdio>
#include<algorithm>
using namespace std;
int v[100001],i,j,n,m,k;
void adun(int poz,int nr)
    {
    int C=0;
    while(poz<=n)
        {
        v[poz]+=nr;
        while(!(poz&(1<<C)))
            C++;
        poz+=(1<<C);
        C++;
        }
    }
int v1(int poz)
    {
    int C=0,S=0;
    while(poz>0)
        {
        S+=v[poz];
        while(!(poz&(1<<C)))
            C++;
        poz-=(1<<C);
        C++;
        }
    return S;
    }
int v2(int sum)
    {
    int pos=n+1,B;
    int st=0,dr=n+1;
    B=n;
    int S=v1(B);
    if(S==sum)
        pos=n;
    while(B)
        {
        B=(st+dr)/2;
        S=v1(B);
        if(S>sum)
            {
            if(dr>B)
                dr=B;
            B--;
            }
        else
            if(S==sum)
                {
                pos=(min(pos,B));
                dr=B;
                B--;
                }
            else
                {
                if(st<B)
                    st=B;
                B++;
                }
        if(B<=st)
            break;
        if(B>=dr)
            break;
        }
    if(pos==n+1)
        return -1;
    return pos;
    }
int main ()
{
freopen("aib.in","r",stdin);
freopen("aib.out","w",stdout);
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
    {
    scanf("%d",&k);
    adun(i,k);
    }
for(i=1;i<=m;i++)
    {
    int qq,k1,k2;
    scanf("%d",&qq);
    if(qq==0)
        {
        scanf("%d%d",&k1,&k2);
        adun(k1,k2);
        }
    if(qq==1)
        {
        scanf("%d%d",&k1,&k2);
        printf("%d\n",v1(k2)-v1(k1-1));
        }
    if(qq==2)
        {
        scanf("%d",&k1);
        printf("%d\n",v2(k1));
        }
    }
return 0;
}