#include<fstream>
using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");
int v[100005], n, m, val, poz, a, b, op;
void update( int x, int p ){
    for( ; p <= n; p += ( p & -p ) ){
        v[p] += x;
    }
    return ;
}
int query( int p ){
    int sum = 0;
    for( ; p >= 1; p -= ( p & -p ) ){
        sum += v[p];
    }
    return sum;
}
int main(){
    fin >> n >> m;
    for( int i = 1; i <= n; i++ ){
        fin >> val;
        update( val, i );
    }
    for( int i = 1; i <= m; i++ ){
        fin >> op;
        if( op == 0 ){
            fin >> poz >> val;
            update( val, poz );
        }
        if( op == 1 ){
            fin >> a >> b;
            fout << query( b ) - query( a - 1 ) << "\n";
        }
        if( op == 2 ){
            fin >> a;
            int st = 1;
            int dr = n;
            while( st <= dr ){
                int mid = ( st + dr ) / 2;
                int sol = query( mid );
                if( sol == a ){
                    fout << mid << "\n";
                    break;
                }
                if( sol < a ){
                    st = mid + 1;
                }else{
                    dr = mid - 1;
                }
            }
            if( st > dr ){
                fout << "-1\n";
            }
        }
    }
    return 0;
}