#include <fstream>

#define zero(x) (x&(-x))
#define NMax 100005
using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");

int n,m,x,c,a,b;
int AIB[NMax];
void add(int x, int poz){
    for(int i = poz; i <= n; i += zero(i))
        AIB[i] += x;
}
int sumpoz(int poz){
    int sum = 0;
    for(int i = poz; i >= 1; i -= zero(i))
        sum += AIB[i];
    return sum;
}
int caut(int k){
    int lo = 1, hi = n,mij = (lo + hi) / 2;
    while(lo <= hi){
        int mij = (lo + hi) / 2;
        int s = sumpoz(mij);
        if(s == k){
            return mij;
        }
        if(s > k){
            hi = mij - 1;
        }
        if(s < k){
            lo = mij + 1;
        }
    }
    return 1;
}
int main()
{
    f >> n >> m;
    for(int i = 1; i <= n; ++i){
        f >> x;
        add(x,i);
    }
    for(int i = 1; i <= m; ++i){
        f >> c >> a;
        if(c == 0){
            f >> b;
            add(b,a);
        }
        if(c == 1){
            f >> b;
            g << sumpoz(b) - sumpoz(a - 1) <<"\n";
        }
        if(c == 2){
            g << caut(a) <<"\n";
        }
    }
    return 0;
}