#include <bits/stdc++.h>
using namespace std;

ifstream fin("aib.in");
ofstream fout("aib.out");

int aib[100005];
int n,q,p,x,y,c;

void Update(int p,int v){
    while(p<=n){
        aib[p]+=v;
        p+=p&(-p);
    }
}

int Query(int p){
    int s=0;
    while(p>=1){
        s+=aib[p];
        p-=p&(-p);
    }
    return s;
}

int main()
{
    int i;
    fin >> n >> q;
    for(i=1;i<=n;i++){
        fin >> x;
        Update(i,x);
    }
    while(q--){
        fin >> c;
        if(c==0){
            fin >>x >> y;
            Update(x,y);
        }
        else if(c==1){
            fin >> x >> y;
            fout << Query(y)-Query(x-1) << "\n";
        }
        else{
            fin >> x;
            int st=1,dr=n,m;
            p=-1;
            while(st<=dr && p==-1){
                m=(st+dr)/2;
                if(x==Query(m)) p=m;
                else if(x>Query(m)) st=m+1;
                else dr=m-1;
            }
            fout << p << "\n";
        }
    }
    return 0;
}