/*
/// time = 0.180
#include <cstdio>
#include <cstring>
#include <fstream>

using namespace std;

#define in "aib.in"
#define out "aib.out"
#define dim 100001

inline int Minim(int a, int b) {
       if ( a < b ) return a;
       return b;
}

int N, M, T;
int Arb[dim];
int C, S;

void Update(int,int);
int Query(int);
int Search(int);

int main()
{
    freopen(in,"rt",stdin);
    freopen(out,"wt",stdout);

    memset(Arb,0,sizeof(Arb));
    int K, X, Y;
    scanf("%d%d", &N, &M);
    for ( int i = 1; i <= N; i++ )
    {
        scanf("%d", &T);
        Update(i,T);
    }

    for ( ; M; M-- )
    {
        scanf("%d", &K);

        if ( K < 2 )
        {
             scanf("%d%d", &X, &Y);
             if ( !K ) Update(X,Y);
             else      printf("%d\n", Query(Y)-Query(X-1));
        }
        else
        {
            scanf("%d", &X);

            printf("%d\n", Search(X));
        }
    }

    fclose(stdin);
    fclose(stdout);
    return 0;
}

int Search(int val)
{
    int i, step;

    for ( step = 1; step < N; step <<= 1 );

    for( i = 0; step; step >>= 1 )
    {
         if( i + step <= N)
         {
            if( val >= Arb[i+step] )
            {
                i += step, val -= Arb[i];
                if ( !val ) return i;
            }
         }
    }

    return -1;
}

void Update(int poz, int val)
{
     C = 0;
     while ( poz <= N )
     {
           Arb[poz] += val;
           while ( !(poz & (1<<C)) ) C++;
           poz += (1<<C);
           C += 1;
     }
}

int Query(int poz)
{
    C = 0, S = 0;
    while ( poz > 0 )
    {
          S += Arb[poz];
          while ( !(poz & (1<<C)) ) C++;
          poz -= (1<<C);
          C += 1;
    }

    return S;
}
*/

/// time = 0.156
#include<cstdio>
#define NMAX 100001

using namespace std;

int c[NMAX],n,m,k,i,op,a,b;

void add(int i,int k) {
  while(i<=n) {
    c[i]+=k;
    i+= (i & -i); //(i^(i&(i-1)));
  }
}

int sum(int i) {
  int s=0;
  while(i) {
    s+=c[i];
    i-= (i & -i); //(i^(i&(i-1)));
  }
  return s;
}

inline int sum(int a,int b) { return sum(b)-sum(a-1); }

int poz(int k) {
  int i=0,st=1;
  while(st<k) st<<=1;
  while(st) {
    if((i+st<=n)&&(k>=c[i+st])) {
      i+=st;
      k-=c[i];
      if(!k) return i;
    }
    st>>=1;
  }
  return -1;
}

int main() {
  freopen("aib.in","r",stdin);
  freopen("aib.out","w",stdout);
  scanf("%d%d",&n,&m);
  for(i=1;i<=n;i++) c[i]=0;
  for(i=1;i<=n;i++) { scanf("%d",&k); add(i,k); }
  for(i=0;i<m;i++) {
    scanf("%d%d",&op,&a);
    if(op!=2) scanf("%d",&b);
    switch(op) {
      case 0: add(a,b); break;
      case 1: printf("%d\n",sum(a,b)); break;
      case 2: printf("%d\n",poz(a)); break;
    }
  }

  fclose(stdin);
  fclose(stdout);
  return 0;
}

/*
/// time = 0.140
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

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

class Fenwick {
public:
    Fenwick( int n ) :n(n) {
        a.resize(n+1);
        for (int i = 1; i <= n; ++i) {
            fin >> a[i];
        }
        for (msb = 1; msb <= n; msb <<= 1);
        msb >>= 1;

        for (int stp = 2; stp <= n; stp<<=1)
            for (int i = stp; i <= n; i += stp)
                a[i] += a[i-(stp>>1)];
    }

    inline void update( int lo, int val ) {
        for (; lo <= n; lo += (lo & -lo))
            a[lo] += val;
    }

    inline int getsum( int lo, int hi ) {
        return getsum(hi)-getsum(lo-1);
    }

    inline int getsum( int hi ) {
        int sum = 0;
        for (; hi > 0; hi &= hi-1)
            sum += a[hi];
        return sum;
    }

    int idx_with_sum( int sum ) {
        int idx = 0;
        for (int stp = msb; stp > 0; stp >>= 1) {
            idx += stp;
            if (idx <= n && sum >= a[idx]) {
                sum -= a[idx];
                if (sum == 0) return idx;
            }
            else idx -= stp;
        }
        return -1;
    }

    vector<int> a;
    int n;
    int msb;
};

int main() {
    int n, m;
    fin >> n >> m;

    Fenwick bit(n);
    int op, lo, hi, val;

    for (int i = 0; i < m; ++i) {
        fin >> op;
        if (op == 0) {
            fin >> lo >> val;
            bit.update(lo, val);
        }
        else if (op == 1) {
            fin >> lo >> hi;
            fout << bit.getsum(lo, hi) << '\n';
        }
        else if (op == 2) {
            fin >> val;
            fout << bit.idx_with_sum(val) << '\n';
        }
    }

    fin.close();
    fout.close();
    return 0;
}
*/