//https://www.infoarena.ro/problema/aib
#include <iostream>
using namespace std;

#define endl '\n'
int n, m, aib[100001];
void update(int ind, int x){
    for (int i=ind; i<=n; i+=i&-i){
        aib[i]+=x;
    }
}
int query(int ind){
    int sum=0;
    for (int i=ind; i>=1; i-=i&-i){
        sum+=aib[i];
    }
    return sum;
}
int binsearch(int x){
    int st=1, dr=n;
    while (st<=dr){
        int mij=(st+dr)/2, q=query(mij);
        if (q==x)return mij;
        if (q<x){
            st=mij+1;
        } else {
            dr=mij-1;
        }
    }
    return -1;
}
int main(){
    freopen("aib.in", "r", stdin);
    freopen("aib.out", "w", stdout);
    cin>>n>>m;
    for (int i=1; i<=n; ++i){
        int x;
        cin>>x;
        update(i, x);
    }
    while (m--){
        int op, x, y;
        cin>>op>>x;
        switch(op){
        case 0:
            cin>>y;
            update(x, y);
            break;
        case 1:
            cin>>y;
            cout<<query(y)-query(x-1)<<endl;
            break;
        case 2:
            cout<<binsearch(x)<<endl;
            break;
        }
    }
}