#include <iostream>
#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;

#define MAXN 100000

int v[MAXN+5];
int aib[MAXN+2], n, m;

void update(int i, int val){
  while(i<=n){
    aib[i]+=val;
    i+=(i&-i);
  }
}

int get(int i){
  int sum = 0;
  while(i>0){
    sum+=aib[i];
    i-=(i&-i);
  }
  return sum;
}

int main(){
  FILE *fin, *fout;
  fin = fopen("aib.in", "r");
  fout = fopen("aib.out", "w");
  fscanf(fin, "%d %d\n", &n, &m);
  for(int i=1; i<=n; i++){
    fscanf(fin, "%d ", &v[i]);
    update(i, v[i]);
  }
  for(int i=0; i<m; i++){
    int type, a, b;
    fscanf(fin, "%d %d", &type, &a);
    if(type!=2) fscanf(fin, "%d", &b);
    switch(type){
      case 0:
        update(a, b);
      break;
      case 1:
        fprintf(fout, "%d\n", get(b)-get(a-1));
        break;
      case 2:
        int s=0, d=n+1;
        while(d-s>1){
          int m = (s+d)/2;
          if(get(m)>a)
            d = m;
          else s = m;
        }
        if(get(s)!=a)
          fprintf(fout, "-1\n");
        else
          fprintf(fout, "%d\n", s);
    }
  }
  return 0;
}