#include <bits/stdc++.h>
#define nmax 100001
#define ui unsigned int
using namespace std;

int aib[nmax],n,m;

ifstream f("aib.in");
ofstream g("aib.out");

void update(ui val,ui pos)
{
    while(pos<=n)
    {
        aib[pos]+=val;
        pos+=(pos&-pos);
    }
}

int query(ui dr)
{
    ui ans=0;
    while(dr)
    {
        ans+=aib[dr];
        //cout<<ans<<' '<<dr<<'\n';
        dr-=(dr&-dr);
    }
    //cout<<'\n';
    return ans;
}

int query2(ui st, ui dr,ui k)
{
    ui mid=(st+dr)/2;
    ui sum=query(mid);
    if(sum==k) return mid;
    if(st==dr&&sum!=k) return -1;
    if(sum<k) return query2(mid+1,dr,k);
    return query2(st,mid,k);
}

int main()
{
    f>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int nr; f>>nr;
        update(nr,i);
    }
    for(int i=0;i<m;i++)
    {
        ui p,a,b; f>>p;
        switch(p)
        {
        case 0:
            f>>a>>b;
            update(b,a);
            break;
        case 1:
            f>>a>>b;
            g<<query(b)-query(a-1)<<'\n';
            break;
        case 2:
            f>>a;
            g<<query2(1,n,a)<<'\n';
        }
    }
    return 0;
}