#include <fstream>

using namespace std;

int aib[15001], n;

void update( int poz, int val ) {
    while(poz<=n) {
        aib[poz] += val;
        poz = poz + (poz&(-poz));
    }
    return;
}

int findSum( int dr ) {
    int s = 0;
    while( dr ) {
        s += aib[dr];
        dr -=(dr&(-dr));
    }
    return s;
}

int query( int st, int dr ) {
    return findSum( dr ) - findSum( st - 1 );
}

int main() {
    ifstream cin("aib.in");
    ofstream cout("aib.out");
    int m, i, p, a, b, st, dr, mij, last;
    cin>>n>>m;
    for( i = 1; i <= n; i++ ) {
        cin>>a;
        update( i, a );
    }
    for( i = 1; i <= m; i++ ) {
        cin>>p;
        cin>>a;
        if( p == 1 ) {
            cin>>b;
            cout<<query( a, b )<<"\n";
        } else if( p == 0 ) {
            cin>>b;
            update( a, b );
        } else {
            st = 1;
            dr = n;
            while( st <= dr ) {
                mij = ( st + dr ) / 2;
                b = findSum( mij );
                if( a == b )
                    last = mij;
                if( b > a )
                    dr = mij - 1;
                else
                    st = mij + 1;
            }
            cout<<last<<"\n";
        }
    }
    return 0;
}