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

/**
8
3 1 6 5 2 7 4 8

0 0 2 2 1 5 3 7

    1 2 3 4 5 6 7
a = 1 0 1 0 1 1 0

nr baza_2  interval  suma
1   0001    [1,1]     1
2   0010    [1,2]     1
3   0011    [3,3]     1
4   0100    [1,4]     2
5   0101    [5,5]     1
6   0110    [5,6]     2
7   0111    [7,7]     0
8   1000    [1,8]     4

42 = [41,42] [33,40] [1,32]

aib[i] = suma elementelor din a[] din
   intervalul [i-2^k+1..i], unde k este
   numarul de biti de 0 cu care se termina i
76543210
10100000 160 = 2^7+2^5
*/

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

int aib[100003], n;

/// ret. suma pe intervalul [1..k]
int Suma(int k)
{
    int s = 0;
    while (k > 0)
    {
        s += aib[k];
        /***
        int x = k;
        int p = 1;
        while (x % 2 == 0)
        {
            x /= 2;
            p = p * 2;
        }
        k -= p;
        */
        k = k - (k&-k);
    }
    return s;
}

void Update(int k, int val)
{
    while (k <= n)
    {
        aib[k] += val;
        k = k + (k & -k);
    }
}

int CB (int suma)
{
    int st = 0, dr = n, mij, p = -1;
    while (st <= dr)
    {
        mij = (st + dr) / 2;
        if (Suma(mij) == suma)
        {
            dr = mij - 1;
            p = mij;
        }
        else if (Suma(mij) > suma)
            dr = mij - 1;
        else st = mij + 1;
    }
    return p;
}

int main()
{
    int Q;
    int i, k;
    fin >> n >> Q;
    for (i = 1; i <= n; i++)
    {
        fin >> k;
        Update(i, k);
    }
    for (int i = 1; i <= Q; i++)
    {
        int task;
        int x, y;
        fin >> task;
        if (task == 0)
        {
            fin >> x >> y;
            Update(x, y);
        }
        else if (task == 1)
        {
            fin >> x >> y;
            fout << Suma(y) - Suma(x - 1) << "\n";
        }
        else
        {
            fin >> x;
            fout << CB(x) << "\n";
        }

    }
    return 0;
}