#include <fstream>
#define zero(x) ((x ^ ( x - 1 ) ) & x )
using namespace std;
ofstream fout ("aib.out");
ifstream fin ("aib.in");
int aib[100005],n,q,a,b;
int ad (int poz , int val)
{
    for( ; poz <= n ; poz += zero(poz))
        aib[ poz ] += val;
    return 1;
}
int queri (int poz)
{
    int suma = 0;
    for( ; poz > 0 ; poz -= zero(poz))
        suma += aib[ poz ];
    return suma;
}
int caut(int val)
{
    int st = 1;
    int dr = n;
    //fout<<st<<" "<<dr<<'\n';
    while(st <= dr)
    {
        int mij =( st + dr ) / 2;
        int aux = queri( mij );
        if ( aux == val )
        {
            fout<<mij<<'\n';
            return 1;
        }
        else if ( aux < val) st = mij + 1;
        else dr = mij - 1;
    }
    fout<<-1<<'\n';
    return 0 ;
}
int main()
{
    fin>>n>>q;
    for(int i = 1 ; i <= n ; i++)
    {
        int aux;
        fin>>aux;
        ad( i , aux );
    }

    for(int i = 1 ; i <= q ; i++)
    {
        int aux ;
        fin>>aux;
        //fout<<aux<<'\n';
        if( aux == 0)
        {
            fin>>a>>b;
            ad( a , b);
        }
        else if (aux == 1)
        {
            fin>>a>>b;
            fout<<queri( b ) - queri( a - 1 )<<'\n';
        }
        else if ( aux == 2)
        {
            fin>>a;
            caut( a );
        }
    }
    return 0;
}