/*https://www.topcoder.com/community/competitive-programming/tutorials/binary-indexed-trees/
op-0 si op-1 = log2(n)
op-2 = log2(n) cu cautare binara pe biti, tot pe topcoder*/

#include <iostream>
#include <fstream>
#include <math.h>
#define DIM 100005

using namespace std;

ifstream f("aib.in");
ofstream g("aib.out");

int N,M, tree[DIM];

int secv(int ind){
    int sum = 0, c = 0;
    while(ind > 0){
        sum += tree[ind];
        while(!(ind & (1 << c)))
            c++;
        ind -= (1 << c);
        c++;
    }
    return sum;
}

void update(int tree[], int ind, int key){
    int MaxInd = N, c = 0;
    while(ind <= MaxInd){
        tree[ind] += key;
        int c=0;
        while(!(ind & (1 << c)))
            c++;
        ind += (1 << c);
        c++;
    }
}

int cautare(int key) {
  int bitMask = pow(2, int(log2(N))); // cea mai mare putere a lui 2 < N
  int ind = 0;
  while(bitMask != 0){
    int indT = ind + bitMask;
    bitMask >>= 1;
    if(indT <= N){
        if(tree[indT] == key)
            return indT;
        else if(key > tree[indT]){
            ind = indT;
            key -= tree[indT];
        }
    }
  }
  if(key != 0)
    return -1;
  return ind;
}

int main()
{
    f>>N>>M;
    int val;
    for(int i=1; i<=N; i++){
        f>>val;
        update(tree,i,val);
    }
    int op,a,b;
    for(int i=1; i<=M; i++){
        f>>op;
        if(op < 2){
            f>>a>>b;
            if(op == 0)
                update(tree,a,b);
            else
                g<<secv(b) - secv(a-1)<<"\n";
        }
        else{
            f>>a;
            g<<cautare(a)<<"\n";
        }
    }
}