#include <bits/stdc++.h>
#define NM 100010
using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");
int aib[NM],n,m,i,t,a,b,st,dr,mij,ans,x;
void update(int pos,int val)
{
    int i;
    for(i=pos;i<=n;i=i+(i&(-i)))
        aib[i]+=val;
}
int query(int pos)
{
    int ans=0,i;
    for(i=pos;i>=1;i=i-(i&(-i)))
        ans+=aib[i];
    return ans;
}
int main()
{
    fin>>n>>m;
    for(i=1;i<=n;i++)
    {
        fin>>x;
        update(i,x);
    }
    for(i=1;i<=m;i++)
    {
        fin>>t>>a;
        if(t==0)
        {   fin>>b;
            update(a,b);
        }
        if(t==1)
        {   
            fin>>b;
            fout<<query(b)-query(a-1)<<'\n';
        }
        if(t==2)
        {
            st=1;
            dr=n;
            int best=-1;
            while(st<=dr)
            {
                mij=(st+dr)/2;
                ans=query(mij);
                if(ans==a)
                {
                    best=mij;
                    break;
                }
                if(ans>a)
                    dr=mij-1;
                else
                    st=mij+1;
            }
            fout<<best<<'\n';
        }
    }
}