#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[100005];
void update(int pos,int val)
{
    int i;
    for(i=pos;i<=100005;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 l,int r,int k)
{
    int st=l,dr=r,mid,keep;
    while(st<=dr)
    {
        mid=(st+dr)/2;
        if(query(mid)==k){keep=mid;break;}
        else if(query(mid)>k)
        {
            dr=mid-1;
        }
        else
        {
            st=mid+1;
        }
    }
    return keep;
}
int main()
{
    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;
            fout<<cautbin(1,n,k)<<'\n';
        }
    }
    return 0;
}