#include <stdio.h>
#include <stdlib.h>
#define zero(x) (x&(-x))
int aib[100001];

inline void update(int poz, int val, int n){
  for(poz; poz<=n; poz+=zero(poz))
    aib[poz]+=val;
}

inline int suma(int poz){
  int sum=0;
  for(poz; poz>0; poz-=zero(poz))
    sum+=aib[poz];
  return sum;
}

inline int cautBin(int val, int n){
  int b=1, e=n, m, x;
  while(b<=e){
    m=(b+e)/2;
    x=suma(m);
    if(x==val)
      return m;
    else if(x<val)
      b=m+1;
    else
      e=m-1;
  }
  return -1;
}

int main()
{
    FILE *fin, *fout;
    int n, m, i, op, a, b;
    fin=fopen("aib.in", "r");
    fscanf(fin, "%d%d", &n, &m);
    for(i=1; i<=n; i++){
      fscanf(fin, "%d", &a);
      update(i, a, n);
    }
    fout=fopen("aib.out", "w");
    for(i=0; i<m; i++){
      fscanf(fin, "%d%d", &op, &a);
      switch(op){
        case 0: fscanf(fin, "%d", &b);
                update(a, b, n);
                break;
        case 1: fscanf(fin, "%d", &b);
                fprintf(fout, "%d\n", suma(b)-suma(a-1));
                break;
        case 2: fprintf(fout, "%d\n", cautBin(a, n));
                break;
      }
    }
    fclose(fout);
    return 0;
}