#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

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

int N, M;
vector<int> aib;

void Read();
void Add( int x, int p );
int Sum( int a, int b );
int Pos( int a );
int Saib( int x );

int main()
{
    int t, x, y;
    Read();
    while ( M-- )
    {
        fin >> t;
        if ( t <= 1 )
            fin >> x >> y;
        else
            fin >> x;

        if ( t == 0 )
            Add(y, x);
        if ( t == 1 )
            fout << Sum(x, y) << '\n';
        if ( t == 2 )
            fout << Pos(x) << '\n';

     /*   for ( int i = 1; i <= N; ++i )
            fout << a[i] << ' ';
        fout << '\n';   */
    }

    fin.close();
    fout.close();
    return 0;
}

void Read()
{
    fin >> N >> M;
    int x;
    aib = vector<int>(N + 1);
    for ( int i = 1; i <= N; ++i )
    {
        fin >> x;
        Add(x, i);
    }

 //   for ( int i = 1; i <= N; ++i )
 //       fout << a[i] << ' ';
}

void Add( int x, int p )
{
    for ( int i = p; i <= N; i += i & -i )
        aib[i] += x;
}

int Sum( int a, int b )
{
    return Saib(b) - Saib(a - 1);
}

int Pos( int a )
{
    int st{1}, dr{N}, mij, r{-1};
    while ( st <= dr )
    {
        mij = ( st + dr ) / 2;
        if ( Saib(mij) > a )
            dr = mij - 1;
        else
            if ( Saib(mij) < a )
                st = mij + 1;
            else
            {
                r = mij;
                dr = mij - 1;
            }
    }

    return r;
}

int Saib( int x )
{
    int s{0};
    for ( int i = x; i >= 1; i -= i & -i )
        s += aib[i];
    return s;
}