#include <stdio.h>
#define N 100010
using namespace std;

int n,m;
int S[N];

FILE *f,*g;

void update(int poz, int nr)
{
    while (poz<=n)
    {
        S[poz]+=nr;
        poz=poz+(poz & (poz ^ (poz-1)));
    }
}

int query(int poz)
{
    long long s=0;
    while (poz>0)
    {
        s+=S[poz];
        poz=poz-(poz & (poz ^ (poz-1)));
    }
    return s;
}

void read()
{
    int i,x;
    fscanf(f,"%d %d",&n,&m);
    for (i=1;i<=n;++i)
    {
        fscanf(f,"%d",&x);
        update(i,x);
    }
}

int bs(int nr)
{
    int st,dr,mij;
    int s;
    st=1;
    dr=n;
    while (st<=dr)
    {
        mij=(st+dr)/2;
        s=query(mij);
        if (s<nr)
            st=mij+1;
        else if (s>nr)
            dr=mij-1;
        else break;
    }
    if (s==nr)
        return mij;
    return -1;
}

void solve()
{
    int i,tip;
    int poz,nr;
    int st,dr;
    S[0]=0;
    for (i=1;i<=m;++i)
    {
        fscanf(f,"%d",&tip);
        if (tip==0)
        {
            fscanf(f,"%d %d",&poz,&nr);
            update(poz,nr);
        }
        else if (tip==1)
        {
            fscanf(f,"%d %d",&st,&dr);
            fprintf(g,"%d\n",query(dr)-query(st-1));
        }
        else if (tip==2)
        {
            fscanf(f,"%d",&nr);
            fprintf(g,"%d\n",bs(nr));
        }
    }
}

int main()
{
    f=fopen("aib.in","r");
    g=fopen("aib.out","w");
    read();
    solve();
    fclose(f);
    fclose(g);
    return 0;
}