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

/**
Arbori indexati binar

Se da un vector a=a1, a2, ..., an
si m operatii de forma:
0. (0 p x) : aduna valoarea x la a[p]
1. (1 i j) : care este suma a[i]+a[i+1]+...+a[j]?
2. (2 s) : care este cea mai din stanga
   poz. p cu a[1]+...+a[p]=s?
Trebuie sa raspundem la operatiile de tip 1
 si 2.

a = 1,2,3,4,0,0,0,8
m=5
1 3 3
1 4 5
2 3 8
1 5 1
2 4 7

a = 1,2,6,4,5,6,7,8
a = 1,2,6,9,5,6,7,8
41
a = 1,2,6,9,6,6,7,8
28

construim vectorul a astfel incat
aib[i] = suma pe un interval de lungime putere a lui 2
      Mai precis, a[i]=suma a[i+1-2^k]..a[i],
      unde k este numarul de biti terminali de 0
      din reprezentarea lui i in baza 2

a = 1,2,3,4,5,6,7,8
aib = 1,3,3,10,5,11,7,36

i  i(baza2)   intervalul    suma
1   0001        [1,1]       1
2   0010        [1,2]       3
3   0011        [3,3]       3
4   0100        [1,4]       10
5   0101        [5,5]       5
6   0110        [5,6]       11
7   0111        [7,7]       7
8   1000        [1,8]       36

n = 100
suma a[43] + ... + a[88] =
a[1]+...+a[88] - (a[1]+...+a[42])

a[1]+...+a[88] = aib[88]+aib[80]+aib[64]
a[1]+...+a[42] = aib[42]+aib[40]+aib[32]

a[18]++
aib[18]++
aib[20]++
aib[24]++
aib[32]++
aib[64]++
*/
class AIB
{
private:
    int aib[100002];
    int n;
public:
    AIB(int dim)
    {
        n = dim;
        for (int i = 1; i <= n; i++)
            aib[i] = 0;
    }
    void Update(int p, int x)
    {
        while (p <= n)
        {
            aib[p] += x;
            /**
            /// calc. k
            int doilak = 1;
            while (p % doilak == 0)
                doilak *=2;
            doilak /= 2;
            p -= doilak;
            */
            p += (p & (-p));
        }
    }

    /// ret. suma elem. de la 1 la p
    int Query(int p)
    {
        int suma = 0;
        while (p > 0)
        {
            suma += aib[p];
            p -= (p & (-p));
        }
        return suma;
    }

    /// ret. cea mai din stanga pozitie p
    /// cu a[1]+...+a[p]=s,
    /// sau -1 daca nu exista o astfel de
    ///   pozitie
    int CautBin(int s)
    {
        int st, dr, p, mij, x;
        st = 1; dr = n; p = -1;
        while (st <= dr)
        {
            mij = (st + dr) / 2;
            x = Query(mij);
            if (x >= s)
            {
                if (x == s) p = mij;
                dr = mij - 1;
            }
            else st = mij + 1;
        }
        return p;
    }
};

int main()
{
    int i, n, m, op, x, y;
    ifstream fin("aib.in");
    ofstream fout("aib.out");
    fin >> n >> m;
    AIB w(n);
    for (i = 1; i <= n; i++)
    {
        fin >> x;
        w.Update(i, x);
    }
    for (i = 1; i <= m; i++)
    {
        fin >> op;
        if (op == 0)
        {
            fin >> x >> y;
            w.Update(x, y);
        }
        else if (op == 1)
        {
            fin >> x >> y;
            fout << w.Query(y) - w.Query(x-1)<<"\n";
        }
        else /// op == 2
        {
            fin >> y;
            fout << w.CautBin(y) << "\n";
        }
    }
    fout.close();
    return 0;
}