#include <bits/stdc++.h>
using namespace std;
ifstream in ("aib.in") ;
ofstream out ("aib.out") ;
int aib [ 100005 ] , aibSize , n , q ;

int suma(int x) {
    int s = 0;
    while (x) {
      s += aib[x];
      x &= x - 1;
    }
    return s;
  }

void adauga(int val, int x) {
    do {
      aib[x] += val;
      x += x & -x;
    } while (x <= aibSize);
  }

 int cautaSP(int val) {
    int x = 0;
    int interval = n / 2;
    while (interval) {
      if (aib[x + interval] < val) {
        val -= aib[x + interval];
        x += interval;
      }
      interval >>= 1;
    }
    return x;
  }

int main ()
{
    in >> n >> q ;
    aibSize = n ;
    for ( int i = 1 ; i <= n ; ++ i )
    {
        int p ;
        in >> p ;
        adauga(p , i ) ;
    }
    while ( q -- )
    {
        int tip ;
        in >> tip ;
        if ( tip == 0 )
        {
            int pos , val ;
            in >> pos >> val ;
            adauga( val , pos ) ;
        }
        if ( tip == 1 )
        {
            int p1 , p2 ;
            in >> p1 >> p2 ;
            out << suma(p2 ) - suma(p1-1) << '\n' ;
        }
        if ( tip == 2 )
        {
            int k ; in >> k ;
            out << cautaSP( k ) + 1 << '\n' ;
        }
    }
}