#include <bits/stdc++.h>

using namespace std;
ifstream r("aib.in");
ofstream w("aib.out");
int v[100001], n, m, aib[100001];
void update(int a, int b){
    aib[a]+=b;
    if(a+ (a & -a)>n){
        return ;
    }
    update(a+ (a & -a), b);
}
int querry(int a){
    if(a - (a & -a) == 0){
        return aib[a];
    }
    return aib[a]+querry(a - (a & -a));
}
int cautbin(int a){
    int pos = -1, step=1;
    while(step*2<=n){
        step*=2;
    }
    while(step>0){
        if(pos+step <= n && querry(pos+step) <= a){
            pos+=step;
        }
        step/=2;
    }
    if(pos != -1 && pos!=0 && querry(pos) == a){
        return pos;
    }
    return -1;
}
int main()
{
    r>>n>>m;
    for(int i=1;i<=n;i++){
        int x;
        r>>x;
        update(i, x);
    }
    for(int i=0;i<m;i++){
        int t;
        r>>t;
        if(t==0){
            int a, b;
            r>>a>>b;
            update(a, b);
        }
        if(t==1){
            int a, b;
            r>>a>>b;
            w<<querry(b)-querry(a-1)<<"\n";
        }
        if(t==2){
            int a;
            r>>a;
            w<<cautbin(a)<<"\n";
        }
    }
    return 0;
}