#include <iostream>
#include <fstream>

#define nMax 100005
#define ll long long

using namespace std;

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

int n, q, c, x, y;

ll aib[nMax];

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

ll query(int x){
    ll s=0;
    for(int i=x;i>0;i-=i&-i)
        s+=aib[i];
    return s;
}

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

    return 0;
}