#include <bits/stdc++.h>

using namespace std;
#define ll long long
ifstream fin("aib.in");
ofstream fout("aib.out");

struct nod{
    int value,left_bound,right_bound;
    nod *left_child,*right_child;
};

nod* create_nod(int left_bound,int right_bound)
{
    nod *q=new nod;
    q->left_bound=left_bound;
    q->right_bound=right_bound;
    int x;
    if(right_bound==left_bound)
    {
        fin>>x;
        q->value=x;
        q->left_child=NULL;
        q->right_child=NULL;
        return q;
    }
    int mij=(left_bound+right_bound)/2;
    q->left_child=create_nod(left_bound,mij);
    q->right_child=create_nod(mij+1,right_bound);
    q->value=q->left_child->value+q->right_child->value;
    return q;
}

void free_nod(nod *r)
{
    if(r==NULL)
        return;
    free_nod(r->left_child);
    free_nod(r->right_child);
    delete r;
}

void update(nod *r,int pos,int val)
{
    if(pos<r->left_bound || pos>r->right_bound)
        return;
    if(r->left_bound==r->right_bound)
    {
        r->value=val+r->value;
        return;
    }
    update(r->left_child,pos,val);
    update(r->right_child,pos,val);
    r->value=r->left_child->value+r->right_child->value;
}

ll query(nod *r,ll a, ll b)
{
    if(r->right_bound<a || r->left_bound>b)
        return 0;
    if(r->left_bound>=a && r->right_bound<=b)
        return r->value;
    ll s1 = query(r->left_child,a,b);
    ll s2 = query(r->right_child,a,b);
    return s1+s2;
}
int main()
{
    ll n,m;
    fin>>n>>m;
    ll c,x,y,z;
    nod *q=create_nod(1,n);
    for(int i=1;i<=m;i++)
    {
        fin>>c;
        if(c==0 || c==1)
        fin>>x>>y;
        else if(c==2)
            fin>>z;
        if(c==0)
            update(q,x,y);
        if(c==1)
            fout<<query(q,x,y)<<"\n";
        if(c==2)
        {
            int st=1,dr=n,poz=-1;
            if(z<query(q,1,1))
            {
                fout<<-1<<"\n";
            }
            else{
                while(st<=dr)
                {
                    ll mij=st+(dr-st)/2;
                    if(z>query(q,1,mij))
                        st=mij+1;
                    else if(z<query(q,1,mij))
                        dr=mij-1;
                    else if(z==query(q,1,mij)){
                            poz=mij;
                            dr=mij-1;
                    }
                }
                fout<<poz<<"\n";
            }
        }

    }

    return 0;
}