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

using namespace std;

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

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

inline void update(int p , int nr) {
    for(int i = p ; i <= n ; i += ZERO(i) )
        aib[i] += nr;
}

inline void construct(int p,int nr) {
    aib[p] += nr;
    if( p + ZERO(p) <=n )
        aib[ p + ZERO(p) ] += aib[p];
}

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 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);
        construct(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;
}