#include <iostream>
#include <fstream>
#define zeros(x) ( (x ^ (x - 1)) & x )

using namespace std;
int n, m, aib[100005], quantity, st, dr, element;

void Add(int x, int quantity)
{
  for(int i = x; i <= n; i += zeros(i))
    aib[i] += quantity;
}
int Compute(int x)
{
  int sum = 0;
  for(int i = x; i >= 1;  i -= zeros(i))
    sum += aib[i];
  return sum;
}
int caut_bin(int x)
{
   st = 0;
   dr = n + 1;
   int mij;
   while(dr - st != 1){
     mij = st + (dr - st) / 2;
     if(Compute(mij) >= x) dr = mij;
       else st = mij;
   }
   if(Compute(dr) != x) return -1;
     else return dr;
}
void AIB()
{
    ifstream fin("aib.in");
    ofstream fout("aib.out");
    fin >> n >> m;
    for(int i = 1; i <= n; ++i){
        fin >> element;
        Add(i, element);
    }

    int type, poz;
    for(int i = 1; i <= m; ++i){
        fin >> type;
        if(type == 0) {
            fin >> poz >> quantity;
            Add(poz, quantity);
        }
        if(type == 1){
            fin >> st >> dr;
            fout << Compute(dr) - Compute(st - 1) << '\n';
        }
        if(type == 2){
            fin >> quantity;
            fout << caut_bin(quantity) << '\n';
        }
    }
}
int main()
{
    AIB();
    return 0;
}