/* 
 * File:   Arboriindexatibinar.cpp
 * Author: slycer
 *
 * Created on December 30, 2011, 7:59 PM
 */

#include <cstdlib>
#include <fstream>
#include <iostream>

using namespace std;

class BIT {
    int *data;
    int n;
public:

    BIT(int n) {
        this->n = n;
        this->data = new int[n + 1];
    }

    void accumulate(int i, int value) {
        while (i <= n) {
            data[i] += value;
            i = i + (i & -i);
        }
    }

    int sum(int i) {
        int ret = 0;
        while (i > 0) {
            ret += data[i];
            i = i - (i & -i);
        }
        return ret;
    }
};

/*
 * 
 */
int main(int argc, char** argv) {

    ifstream input ( "aib.in" );
    ofstream output( "aib.out" );

    int n; 
    int m; 
    input >> n >> m; 
    BIT bit(n);
    for ( int i=1; i<=n; i++){
        int c; 
        input >> c; 
        bit.accumulate(i,c);
       // cout << bit.sum( i ) << endl; 
    }
    for ( int op=1; op<=m; op++){
        int type; 
        input >> type; 
        if ( type == 0 ){
            int i,b;
            input >> i >> b; 
            bit.accumulate( i, b ); 
        }
        if ( type == 1 ){
            int a,b; 
            input >> a >> b; 
            int sol = bit.sum(b) - bit.sum(a-1); 
            output << sol << "\n";
        }
        if ( type == 2 ){
            int b; 
            input >> b; 
            int stanga=1; 
            int dreapta=n; 
            int m; 
            while ( stanga<=dreapta ){
                m = ( stanga + dreapta )/2; 
                if ( bit.sum(m) == b ){
                    break; 
                }
                if ( bit.sum(m) < b ){
                    stanga = m+1; 
                } else{
                    dreapta = m-1; 
                }
            }
            if ( stanga>dreapta ){
                m=-1; 
            }
            output << m << "\n";
        }
    }
    
    return 0;
}