#include <stdlib.h>
#include <cstdio>
#include <algorithm>

using namespace std;

int aib[100001],nr,n,m;

#define ZERO(x)  ( (x ^ (x - 1)) & x )

inline void update(int p , int nr) {

    for(int i = p ; i <= n ; i += ZERO(i) )
        aib[i] += nr;
}

inline int query(int p) {
    int sum = 0;
    for( int i = p ; i > 0 ; i -= ZERO(i) )
        sum += aib[i];
    return sum;
}
/*
int search(int s,int d,int nr) {
    if(s > d) return -1;
    int mij = ( s + d) / 2;
    int sum = query(mij);

    if( sum == nr )
        return max( search(s,mij-1,nr) , mij );

    if(nr < sum)
        return search(s,mij-1,nr);
    else
        return search(mij+1,d,nr);
}
 */

int search(int s,int d,int nr){
    int poz = -1;
    while(s <= d ) {
        int mij = ( s + d ) / 2;
        int sum = query(mij);
        if( sum == nr) { d = mij - 1; poz = mij; }
        if( sum < nr )
            d = mij - 1;
        else
            s = mij + 1;
    }
    return poz;
}

int main(int argc, char** argv) {

    freopen("aib.in","r",stdin);
    freopen("aib.out","w",stdout);

    scanf("%d %d",&n,&m);

    for(int i= 1 ; i <= n ; i++) {
        scanf("%d",&nr);
        update(i,nr);
    }

    for(int i = 1 ; i <= m ; i++) {
        int t,p1,p2;
        scanf("%d",&t);

        if(t==2)
            scanf("%d",&p1);
        else
            scanf("%d %d",&p1,&p2);

        switch (t) {
                case 0 :  update(p1,p2);  break;
                case 1 :  printf("%d\n", query(p2) - query(p1-1)); break;
                case 2 :  printf("%d\n",search(1,n,p1));   break;
        }
    }

    return 0;
}