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

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

/**
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] = 
76543210
10100000 160 = 2^7+2^5

   a =
     5 :   1  (00001) ]  \  \  \ 
     2 :   2  (00010)    /  |  | 
     9 :   3  (00011) ]     |  |
     7 :   4  (00100)       /  |
     5 :   5  (00101) ]  \     |
    20 :   6  (00110)    /     |
    10 :   7  (00111) ]        |
    -7 :   8  (01000)          /
     2 :   9  (01001) ]  \ \     \
     3 :  10  (01010)    / |     |
    -4 :  11  (01011) ]    |     |
     0 :  12  (01100)      /     |
    -2 :  13  (01101) ]  \       |
    15 :  14  (01110)    /       |
     5 :  15  (01111) ]          |

*/
int n, m, ar[100002], aib[100002];

void FenwickMake()
{
    int i, p;
    for (i = 1; i <= n; i++)
        aib[i] = ar[i];
    for (i = 1; i <= n; i++)
    {
        p = i + (i & -i); // indicele parintelui imediat
        if (p <= n)
            aib[p] += aib[i]; 
    }
}

void Add(int i, int val)
{
    while (i <= n) // moficari propagate prin indicii parintelui
    { 
        aib[i] += val; // adauga ultimul bit 7 = 00111 &  |  20   010100 + 
        i += (i & -i); //                   -7 = 11001    | (4)   000100
                       //                        00001    |       011000
    }
}

int Sum(int i)
{
    int sum = 0;
    while (i > 0) // parcurgere inversa 
    {
        sum += aib[i]; 
        i -= (i & -i); // sterge ultimul bit din i 00111 -> 00110 -> 00100 
    }
    return sum;
}

int CautBin(int x)
{
    int st, dr, mij, sum;
    st = 1; dr = n;
    while (st <= dr)
    {
        mij = (st + dr) / 2;
        sum = Sum(mij);
        if (sum == x) return mij;
        else if (sum < x) st = mij + 1;
        else dr = mij - 1;
    }
    return -1;
}

void Fenwick()
{
    int i, a, b, tip;
    fin >> n >> m;
    for (i = 1; i <= n; i++)
        fin >> ar[i];
    FenwickMake();
    for (i = 1; i <= m; i++)
    {
        fin >> tip >> a;
        if (tip == 0)
        {
            fin >> b;
            Add(a, b);
        }
        else if (tip == 1)
        {
            fin >> b;
            if (a > b) swap(a, b);
            fout << Sum(b) - Sum(a - 1) << '\n';
        }
        else fout << CautBin(a) << '\n';
    }
}


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