#include <bits/stdc++.h>

using namespace std;

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

int aib[2000005];
int n,m;

int LSB(int x){
    return (x&(-x));
}

int Query(int x){
    int ans = 0;
    for (int i=x;i>0;i-=LSB(i)){
        ans += aib[i];
    }
    return ans;
}

int Update(int x,int val){
    for (int i=x;i<=(1<<20);i+=LSB(i)){
        aib[i] += val;
    }
}

int BinarySearch(int a){
    int ans = 0,sum = 0;
    for (int pas=(1<<20);pas>0;pas/=2){
        if (sum+aib[pas]<=a){
            ans += pas;
            sum += aib[pas];
        }
    }
}

int main()
{
    fin >> n >> m;
    for (int i=1;i<=n;++i){
        int val;
        fin >> val;
        Update(i,val);
    }
    while (m--){
        int type;
        fin >> type;
        if (type==0){
            int a,b;
            fin >> a >> b;
            Update(a,b);
        }else if (type==1){
            int a,b;
            fin >> a >> b;
            fout << Query(b)-Query(a-1) << '\n';
        }else{
            int a;
            fin >> a;
            fout << BinarySearch(a) << '\n';
        }
    }
    return 0;
}