#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
vector <int> aib;
int n,q;
void update(int i,int val){
    while(i<=n){
        aib[i]+=val;
        i+=i&-i;
    }
}
int prefs(int i)
{
    int sum=0;
    while(i>0){
        sum+=aib[i];
        i=i-(i&-i);
    }
    return sum;
}
int range(int i,int j){
    return prefs(j)-prefs(i-1);
}
int solvek(int k){
    int lf=1,rg=n;
    while(lf<=rg){
        int mid=(lf+rg)/2;
        int z=range(1,mid);
        if(z==k)return mid;
        if(z<k)lf=mid+1;
        if(z>k)rg=mid-1;
    }
    return -1;
}
int main()
{
    ifstream cin("aib.in");
    ofstream cout("aib.out");
    cin>>n>>q;
    aib.resize(n);
    for(int i=1;i<=n;i++){
        int val;
        cin>>val;
        update(i,val);
    }
    for(int i=1;i<=q;i++){
        int a,b,c;
        cin>>a;
        if(a==0){
            cin>>b>>c;
            update(b,c);
        }else if(a==1){
            cin>>b>>c;
            cout<<range(b,c)<<"\n";
        }else{
            cin>>b;
            cout<<solvek(b)<<"\n";
        }
    }
    return 0;
}