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

/**
AIB - Binary Indexed Tree
---------------------------
Se da un sir a1, a2, ..., an de numere intregi.
Operatii:
1 p x : a[p] += x
2 i j : Sa se det. suma a[i]+a[i+1] + ... + a[j]
Se dau: sirul a si M operatii, sa se raspunda la operatiile 2

Construim vectorul aib[] de lungime n in care
aib[i] = a[i - 2^k + 1] + a[i - 2^k + 2] + ... + a[i], unde
       k este numarul de biti de 0 cu care se termina i in baza 2

Ex: a = (1,2,3,4,5,6,7,8)

i  baza 2  a[i - 2^k + 1..i]   aib[i]
--------------------------------------------
1   0001    [1,1]               1       = 1
2   0010    [1,2]               1+2     = 3
3   0011    [3,3]               3       = 3
4   0100    [1,4]               1+2+3+4 = 10
5   0101    [5,5]               5       = 5
6   0110    [5,6]               5+6     = 11
7   0111    [7,7]               7       = 7
8   1000    [1,8]               36      = 36

1 3 1

n=200
1 9 100:
aib[9] += 100  9 = 1001
aib[10] += 100 10 = 1010
aib[12] += 100 12 = 1100
aib[16] += 100 16 = 10000
aib[32] += 100 32 = 100000
aib[64] += 100 64 = 1000000
aib[128] += 100 128 = 10000000


2 2 6 : a[2]+a[3]+a[4]+a[5]+a[6] = a[1]+a[2]+a[3]+a[4]+a[5]+a[6]-a[1]

a[i]+a[i+1] + ...+a[j] = a[1]+...+a[j] - (a[1]+...+a[i-1])

Cum calculez suma de la 1 la 6?
a[1]+a[2]+a[3]+a[4]+a[5]+a[6] = aib[6]+aib[4]

n=200
a[1] + a[2] + ... + a[200]   11001000->11000000

aib[200] + aib[192] + aib[128]

a[1]+...+a[53] = [53,53] + [49,52] + [33,48] + [1,32]

a = 3 4 0 0 1 1 0 0 0 0 5 7 0 2
*/

ifstream fin("aib.in");
ofstream fout("aib.out");
int aib[100002], n;

/// pentru operatia 1 p x : a[p] += x
void Update(int p, int x)
{
    while (p <= n)
    {
        aib[p] += x;
        p += (p & -p); /// p&-p = 2^k
    }
}

/// pentru operatia 2 i j : suma a[1]+...+a[j] si suma a[1]+...+a[i-1]
/// fc ret. suma a[1]+...+a[p]
int Query(int p)
{
    int suma = 0;
    while (p >= 1)
    {
        suma += aib[p];
        p -= (p & -p); /// p&-p = 2^k
    }
    return suma;
}

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

int main()
{
    int i, m, x, y, p, op;
    fin >> n >> m;
    for (i = 1; i <= n; i++)
    {
        fin >> x;
        Update(i, x);
    }
    for (i = 1; i <= m; i++)
    {
        fin >> op;
        if (op == 0)
        {
            fin >> p >> x;
            /// a[p] += x
            Update(p, x);
        }
        else if (op == 1)
        {
            fin >> x >> y;
            fout << Query(y) - Query(x - 1) << "\n";
        }
        else /// op== 2
        {
            fin >> x;
            fout << CautBin(x) << "\n";
        }
    }
    return 0;
}