#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");
int v[150000], n, x, m, a, b, t;
int zeros(int a){
return a&(a-1)^a;
}
void update(int poz, int x){
for(int i=poz; i<=n; i+=zeros(i)){
    v[i]+=x;
    }
//    cout<<"updated:\n";
//        for(int j=1; j<=n; ++j) cout<<v[j]<<' ';
//    cout<<'\n';
}
int querry(int poz){
int sum=0;
for(int i=poz; i>0; i-=zeros(i)){
    sum+=v[i];
}
return sum;
}
int bs(int a, int b){
if(a>b) return -1;

else {int m=(a+b)/2;
int sum=querry(m);
    if(sum==x) {return m;}
    else if(sum<x) return bs(m+1, b);
    else return bs(a, m-1);
    }
}

int search(int x){
int k=2, sum, last=0;
while(last<k){
    sum=querry(k);
    if(sum==x) {return k;}
    else if(sum<x) last=k, k=k<<1;
    else return bs(last+1, k-1);
}

//return -1;
}

int main()
{
f>>n>>m;
for(int i=1; i<=n; ++i){
    f>>x;
   update(i, x);
//    for(int j=1; j<=n; ++j) cout<<v[j]<<' ';
//    cout<<'\n';
}
while(m--){
    f>>t;
    if(t==0) f>>a>>b, update(a, b);
    else if(t==1) f>>a>>b, g<<querry(b)-querry(a-1)<<'\n';
    else {f>>x; g<<search(x)<<'\n'; continue;}

}

//    cout<<"updated:\n";
//        for(int j=1; j<=n; ++j) cout<<v[j]<<' ';
//    cout<<'\n';

    return 0;
}