#include <iostream>
#include <fstream>

using namespace std;

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

const int NMAX = 100003;

int tree[NMAX];
int a[NMAX];

int N, Q;
int task, x, y;

void Update(int pos, int val)
{
    while(pos <= N)
    {
        tree[pos] += val;
        pos += (pos & -pos);
    }
}

int Query(int pos)
{
    int sum = 0;

    while(pos > 0)
    {
        sum += tree[pos];
        pos -= ( pos & -pos);
    }

    return sum;
}

int BinSearch(int lf, int rg, int x)
{
    if(lf > rg) return -1;

    int mid = (lf + rg) / 2;
    int q = Query( mid ) ; //fout << q << " ";

    if(q == x) return mid;

    if(q < x) return BinSearch(mid + 1, rg, x);
    else return BinSearch(lf, mid - 1, x);

}
void Read()
{
    fin >> N >> Q;

    for(int i = 1; i <= N; ++i)
    {
        fin >> a[i];
        Update(i, a[i]);
    }

    for(int i = 1; i <= Q; ++i)
    {
        fin >> task;

        if( task == 0)
        {
            fin >> x >> y; //cout << 0;

            Update(x, y);
        }
        if( task == 1)
        {
            fin >> x >> y; //cout << 1;

            fout << Query( y ) - Query(x - 1) << "\n";
        }
        if( task == 2)
        {
            fin >> x; //cout << 2;

            fout << BinSearch(1, N, x ) << "\n";
        }

    }

    fin.close();
    fout.close();
}
int main()
{
    Read();
    return 0;
}