#include<bits/stdc++.h>
#define NMAX 100001

using namespace std;

ifstream fin("aib.in");
ofstream fout("aib.out");
int aib[NMAX],n,v[NMAX];
void precalc(){
    for(int i=1;i<=n;i++){
        aib[i]=v[i];
        int p=1,first=(i&(i-1));
        while(p<i-first){
            aib[i]+=aib[i-p];
            p*=2;
        }
    }
}
int p2(int x){
    return ((x^(x-1))&x);
}
void actualizare(int p, int x)
{
     int pw=0;
     while(p<=n)
     {
        aib[p]+=x;
        while(!(p&(1<<pw))) pw++;
        p+=(1<<pw);
        pw++;
     }
}

int suma(int p)
{
    int pw=0,S=0;
    while(p>0)
    {
      S+=aib[p];
      while(!(p&(1<<pw))) pw++;
      p-=(1<<pw);
      pw++;
    }
    return S;
}
int binsearch(int a){
    int s=1,d=n,m,sum;
    while(s<d){
        m=(s+d)/2; sum=suma(m);
        if(a>sum)
            s=m+1;
        else if(a<sum)
            d=m-1;
        else
            return m;
    }
    return (s+d)/2;
}
int main()
{
    int m,i,a,b,querytype;
    fin>>n>>m;
    for(i=1;i<=n;i++){
        fin>>v[i];
    }
    precalc();
    for(i=0;i<m;i++){
        fin>>querytype;
        if(querytype==0){
            fin>>a>>b;
            actualizare(a,b);
        }
        else if(querytype==1){
            fin>>a>>b;
            fout<<suma(b)-suma(a-1)<<'\n';
        }
        else{
            fin>>a;
            fout<<binsearch(a)<<'\n';
        }
    }
    return 0;
}