#include <fstream>
#define DIM 100010
using namespace std;

ifstream fin ("aib.in" );
ofstream fout("aib.out");

int N, M, i, j, K, ok, minim;
int AIB[DIM],p, Q, A, B, cod;

int QUERY(int p){
     int sum = 0;
     for(p = p; p != 0; p -= (p & (-p))){
          sum += AIB[p];
     }
     return sum;
}

void UPDATE(int p, int val){
     for(p = p; p <= N; p += (p & (-p))){
          AIB[p] += val;
     }
     return;
}

int CautBin(int val){
     int st = 1;
     int dr = N;
     int mid= 0;
     while(st <= dr){
          mid = st + (dr - st) / 2;
          if(QUERY(mid) == val)
               return mid;
          if(QUERY(mid) < val)
               st = mid + 1;
          else
               dr = mid - 1;
     }
     return -1;
}

void SetUp(){
     fin >> N >> Q;
     for(i = 1; i <= N; i++){
          fin >> A;
          UPDATE(i, A);
     }
     return;
}

int main(){
     SetUp();
     for(i = 1; i <= Q; i++){
          fin >> cod >> A;
          if(cod != 2)
               fin >> B;
          switch(cod)
          {
               case 0:{UPDATE(A, B);break;}
               case 1:{fout<<QUERY(B)-QUERY(A-1)<<"\n";break;}
               case 2:{fout<<CautBin(A)<<"\n";break;}
          }
     }
    return 0;
}