#include <bits/stdc++.h>
using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");
int n,q,i,x,t,y,k,par;
int a[100205];
void update(int pos,int val)
{
    int i;
    for(i=pos;i<=n;i+=(i&(-i)))
        a[i]+=val;
}
int query(int x)
{
    int i,r=0;
    for(i=x;i>=1;i-=(i&(-i)))
        r+=a[i];
    return r;
}
int cautbin(int k)
{
    int st=1,dr=n,mid,keep=-1;
    while(st<=dr)
    {
        mid=(st+dr)/2;
        int cmp=query(mid);
        if(cmp==k)
            keep=mid;
        if(cmp>=k)
        {
            dr=mid-1;
        }
        else
        {
            st=mid+1;
        }
    }
    return keep;
}
int  main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(NULL);
    fout.tie(NULL);
    fin>>n>>q;
    for(i=1;i<=n;i++)
    {
        fin>>x;
        update(i,x);
    }
    for(i=1;i<=q;i++)
    {
        fin>>t;
        if(t==0)
        {
            fin>>x>>y;
            update(x,y);
        }
        else if(t==1)
        {
            fin>>x>>y;
            fout<<query(y)-query(x-1)<<'\n';
        }
        else if(t==2)
        {
            fin>>k;
             int st=1, dr=n, sol=-1;
            while(st<=dr)
            {
                int mij=(st+dr)/2;
                int val=query(mij);
                if(val==k)
                    sol=mij;
                if(k<=val)
                    dr=mij-1;
                else
                    st=mij+1;
            }
            fout<<sol<<'\n';
        }
    }
    return 0;
}