#include <iostream>
#include <fstream>

#define nMax 100001

using namespace std;

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

int n, m, c, x, y, aib[nMax];

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

int query(int poz){
    int sum=0;
    for(int i=poz;i>0;i-=(i&-i))
        sum+=aib[i];
    return sum;
}

int main(){
    fin>>n>>m;
    for(int i=1;i<=n;i++){
        fin>>x;
        update(i, x);
    }

    for(int i=0;i<m;i++){
        fin>>c>>x;
        if(!c){
            fin>>y;
            update(x, y);
        }
        else if(c==1){
            fin>>y;
            fout<<query(y)-query(x-1)<<"\n";
        }
        else{
            int l=1, r=n, mid, rasp=-1;
            while(l<=r)
            {
                mid = (l + r) / 2;
                int val = query(mid);
                if(val==x){
                    rasp=mid;
                    r=mid-1;
                }
                else if(val>x)
                    r=mid-1;
                else l=mid+1;
            }
            fout<<rasp<<'\n';
        }
    }

    return 0;
}