#include <bits/stdc++.h>

using namespace std;

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

int n,q,x,aib[100200];

void update(int p,int x){
    for(int i=p; i<=n; i+=i&-i)
        aib[i]+=x;
}

int query(int p){
    int rez=0;
    for(int i=p; i>=1; i-=i&-i)
        rez+=aib[i];
    return rez;
}

int32_t main()
{
    f>>n>>q;
    for(int i=1; i<=n; i++)
        f>>x, update(i,x);
    for(int i=1; i<=q; i++)
    {
        int op,a,b;
        f>>op>>a;
        if(op==0)
            f>>b, update(a,b);
        if(op==1)
            f>>b, g<<query(b)-query(a-1)<<'\n';
        if(op==2)
        {
            int st=1, dr=n, sol=-1;
            while(st<=dr)
            {
                int mij=(st+dr)/2;
                int val=query(mij);
                if(val==a)
                    sol=mij;
                if(a<=val)
                    dr=mij-1;
                else
                    st=mij+1;
            }
            g<<sol<<'\n';
        }
    }
    return 0;
}