#include <cstdio>

using namespace std;

long long v[100005], s[100005], n;

void up(int i, int k){
  for(;i < n;i += (i&-i))
    v[i] += k;
}

long long sum(long long a){
  long long s;
  s = 0;
  for(;a > 0;a -= (a&-a)){
    s += v[a];
  }
  return s;
}

int bin(int k){
  int st, dr, med, x;
  st = 1;
  dr = n;
  while(st <= dr){
    med = (st + dr) / 2;
    x = sum(med);
    if(x == k){
      return med;
    }
    else
    if(x < k){
      st = med + 1;
    }
    else
      dr = med - 1;
  }
  return -1;
}

int main()
{
    freopen("aib.in", "r", stdin);
    freopen("aib.out", "w", stdout);
    int q, m, i, p, a, b;
    scanf("%d%d", &n, &m);
    for(i = 1;i <= n;i++){
      scanf("%d", &v[i]);
      s[i] = s[i - 1] + v[i];
      v[i] = s[i] - s[i - (i&-i)];
    }
    for(i = 0;i < m;i++){
      scanf("%d", &p);
      if(p == 0){
        scanf("%d%d", &a, &b);
        up(a, b);
      }
      else
      if(p == 1){
        scanf("%d%d", &a, &b);
        printf("%d\n", sum(b) - sum(a - 1));
      }
      else{
        scanf("%d", &a);
        printf("%d\n", bin(a));
      }
    }

    return 0;
}