#include<bits/stdc++.h>
#define Nmax 100100
using namespace std;

int AIB[Nmax], N, M, a, b, t, pw = 1;

inline int zeros(int x) { return x & (-x); }

inline void add(int x, int q) {
	for (int i = x; i <= N; i += zeros(i)) AIB[i]+=q;
}

inline int comp(int x) {
	int ret = 0;
  for (int i = x; i > 0; i -= zeros(i)) {
    ret += AIB[i];
  }
  return ret;
}

inline int caut(int val) {
  int ok = (val == 2560);
  int curr = pw, s = 0, ret = 0;
  while(curr) {
    if(AIB[ret + curr] + s <= val) {
      s += AIB[ret + curr];
      ret += curr;
    }
    curr /= 2;
  }
  if(s != val) return -1;
  return ret;
}

int main() {
  freopen("aib.in","r",stdin);
  freopen("aib.out","w",stdout);
  scanf("%d%d",&N,&M);
  
  while(pw*2 <= N) {
    pw *=2;
  }
  
  for(int i=1;i<=N;++i) {
    scanf("%d",&a);
    add(i,a);
  }  
  
  for(int i=1;i<=M;++i) {
    scanf("%d%d",&t,&a);
    if(t<2) {
      scanf("%d",&b);
      if(t == 0) {
        add(a,b);
      } else {
        printf("%d\n",comp(b)-comp(a-1));
      }
    } else {
      printf("%d\n",caut(a));
    }
  }
  return 0;
}