#include <bits/stdc++.h>
using namespace std;

ifstream fin ("aib.in");
ofstream fout ("aib.out");

int aib[100010],i,j,n,m,k,x,a,b;

void adauga( int poz, int val )
{
    for( ; poz <= n ; poz += poz & ( -poz ) )
        aib[ poz ] += val;
}

int suma( int poz )
{
    int ans = 0;
    for( ; poz >= 1 ; poz -= poz & ( -poz ) )
        ans += aib[ poz ];
    return ans;
}

int primii( int val )
{
    int i,poz = 0;
    for( i = 1 ; i * 2 <= n ; i *= 2 );
    for( ; i >= 1 ; i /= 2 )
        if( aib[ poz + i ] <= val && poz + i <= n )
        {
            val -= aib[ poz + i ];
            poz += i;
        }
    if( val )
        return -1;
    else
        return poz;

}

int main ()
{
    fin>>n>>m;
    for( i = 1 ; i <= n ; i++ )
    {
        fin>>x;
        adauga( i , x );
    }

    for( i = 1 ; i <= m ; i++ )
    {
        fin>>x;
        if( x == 0 )
        {
            fin>>k>>x;
            adauga( k , x );
        }
        else if( x == 1 )
        {
            fin>>a>>b;
            fout<<suma( b ) - suma( a - 1 )<<'\n';
        }
        else
        {
            fin>>x;
            fout<<primii( x )<<'\n';
        }
    }
    return 0;

}