#include <cstdio>

using namespace std;

int a[100005], n;

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

int query(int poz){
  int sum = 0;
  for(;poz > 0;poz -= (poz & -poz))
    sum += a[poz];
  return sum;
}

int med(int k){
  int st = 1, dr = n, med, a;
  while(st <= dr){
    med = (st + dr) / 2;
    a = query(med);
    if(a == k){
      return med;
    }
    else
    if(a > k){
      dr = med - 1;
    }
    else{
      st = med + 1;
    }
  }
  return -1;
}

int main()
{
    freopen("aib.in", "r", stdin);
    freopen("aib.out", "w", stdout);
    int m, x, a, b, i;
    scanf("%d%d", &n, &m);
    for(i = 1;i <= n;i++){
      scanf("%d", &x);
      update(i, x);
    }
    for(i = 0;i < m;i++){
      scanf("%d", &x);
      if(!x){
        scanf("%d%d", &a, &b);
        update(a, b);
      }
      else
      if(x == 1){
        scanf("%d%d", &a, &b);
        printf("%d\n", query(b) - query(a - 1));
      }
      else{
        scanf("%d", &a);
        printf("%d\n", med(a));
      }
    }
    return 0;
}