#include <bits/stdc++.h>
/// CA DOAR UNUL ESTE DUUUUM-NEEE-ZEEEU
#define nmax 100005

using namespace std;

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

int n, k;
int aib[nmax];

/**
    a = a1, a2, ..., an
    op1: (p,x) : a[p] += x;
    op2: (x,y) : a[x] + a[x + 1] + a[x + 2] + ... a[y] = ?

    Complexitate(op1, op2) : O(log N)

    aib[i] = suma elementelor din intervalul [i - 2^k + 1, i]
            k - nr de biti de 0 de la sf reprezentarii lui i in baza 2;


    ex: a = 1, 2, 3, 4, 5, 6, 7, 8

    i   | baza 2 | interval | Suma (aib[i])    op(5, -5)
    ------------------------------------
    1   |    1   | [1,1]    |   1
    2   |   10   | [1,2]    |   3
    3   |   11   | [3,3]    |   3
    4   |  100   | [1,4]    |   10
    5   |  101   | [5,5]    |   5               -> 0
    6   |  110   | [5,6]    |   11              -> 6
    7   |  111   | [7,7]    |   7
    8   | 1000   | [1,8]    |   36              -> 31

    S[3..7] = S[1, 7] - S[1, 2]
    1..7 = 1..4 + 5..6 + 7..7
*/

int Query(int p)
{
    /// care este suma a[1] + a[2] + ... + a[p]?
    int s = 0;
    while(p > 0)
    {
        s += aib[p];
    /// p = p - 2^k - ma duc la poz precedenta din tabel ^.up
    /// k - nr de biti de 0 in care se termina p

        p -= (p & (-p));
        /**
            Este echivalent cu:
                k = 0;
                q = k;
                while(q % 2 == 0)
                {
                    k++:
                    q = q/2;
                }
                p = p - (1 << k);
        */
    }
    return s;
}

int CautaPoz(int s)
{
/**
    O (log^2 n)
    returneaza cea mai din stanga poz p cu
    a1+a2+...+ap = s
*/
    int st, dr, mid, p, suma;
    p = -1;
    st = 1;
    dr = n;
    while (st <= dr)
    {
        mid = (st + dr) / 2;
        suma = Query(mid);
        if (suma == s)
        {
            p = mid;
            dr = mid - 1;
        }
        else if (suma > s)
            dr = mid - 1;
        else st = mid + 1;
    }
    return p;
}

void Update(int p, int x) /// OP2  => adauga x la pozitia P
{
    while(p <= n)
    {
        aib[p] += x;
        p += (p & (-p));
    /// ma duc mai jos in tabel la urm pozitie de actualizat v.down (ex(5, -5): 5 -> 6 -> 8
    }
}

void Citire()
{
    int i, x, op, p, y;
    fin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        fin >> x;
        Update(i, x);
    }
    for (i = 1; i <= k; i++)
    {
        fin >> op;
        if (op == 0)
        {
            fin >> p >> x;
            Update(p, x);
        }
        else if (op == 1)
        {
            fin >> x >> y;
            fout << Query(y) - Query(x - 1) << "\n";
        }
        else
        {
            fin >> x;
            fout << CautaPoz(x) << "\n";
        }
    }
}

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