#include <bits/stdc++.h>

using namespace std;

ifstream f("aib.in");
ofstream g("aib.out");

const int NMAX = 1e5 + 1;

int aib[NMAX];
int n;

void update ( int idx, int val )
{
    for ( int i = idx; i <= n; i += ( i & -i ) )
        aib[i] += val;
}

int compute ( int idx )
{
    int sol = 0;
    for ( int i = idx; i > 0; i -= ( i & -i ) )
        sol += aib[i];
    return sol;
}

int lb ( int x )
{
    int st = 1, dr = n;
    int sol = -1;
    while ( st <= dr )
    {
        int mij = ( st + dr ) / 2;
        int rez = compute( mij );
        if ( rez == x )
            return mij;
        if ( rez < x )
            st = mij + 1;
        else dr = mij - 1;
    }
    return sol;
}

int main()
{
    int q;
    f >> n >> q;
    for ( int i = 1; i <= n; i ++ )
    {
        int x;
        f >> x;
        update ( i, x );
    }
    int t, poz, x, a, b, sum;
    while ( q -- )
    {
        f >> t;
        if ( t == 0 )
        {
            f >> poz >> x;
            update ( poz, x );
        }
        else if ( t == 1 )
        {
            f >> a >> b;
            g << compute ( b ) - compute ( a - 1 ) << '\n';
        }
        else
        {
            f >> sum;
            g << lb ( sum ) << '\n';
        }
    }
    return 0;
}