//#include <iostream>
#include <fstream>
using namespace std;
ifstream cin("aib.in");
ofstream cout("aib.out");

int aib[100005];
int n, m, x, tip, a, b;
// Suma[a, b] = Suma[1, b] - Suma[1, a-1]
int suma(int a, int b) {
    if(a != 1) {
        return suma(1, b) - suma(1, a-1);
    }
    int p = 1 << 17, r = 0, sumaTotala = 0;
    while(p > 0) {
        if(r + p <= b) {
            sumaTotala += aib[r + p];
            r += p;
        }
        p /= 2;
    }
    return sumaTotala;
}

int query(int a, int b) {
    if(a != 1) {
        return query(1, b) - query(1, a-1);
    }
    int sumaTotala = 0;
    while(b > 0) {
        sumaTotala += aib[b];
//        b = (b & (b-1));
        b -= (b & (-b));
    }
    return sumaTotala;
}

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

// 2 a - Sa se determine pozitia minima k astfel
// incat suma valorilor primilor k termeni sa fie exact a.
int query2(int a) {
    int p = 1 << 17, r = 0, sumaTotala = 0, raspuns = -1;
    while(p > 0) {
        if(r + p <= n && sumaTotala + aib[r + p] == a) {
            raspuns = r + p;
        }
        if(r + p <= n && sumaTotala + aib[r + p] < a) {
            sumaTotala += aib[r + p];
            r += p;
        }
        p /= 2;
    }
    return raspuns;
    // r - cea mai mare pozitie cu suma pana acolo mai mica decat a
    // r + 1
//    if(sumaTotala + v[r + 1] == a)
//        return r + 1;
//    else
//        return -1;
}

// b += (b ^ (b & (b - 1)))
// b += (b & (-b))

// a = 0 = 0000000
// a --
// a = -1 = 11111111
//     +1 = 00000000
// 1 = 000001
//     111111

signed main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) {
        cin >> x;
        update(i, x);
    }
    for(int i = 1; i <= m; i ++) {
        cin >> tip;
        if(tip == 0) {
            cin >> a >> b;
            update(a, b);
        } else if(tip == 1) {
            cin >> a >> b;
            cout << query(a, b) << '\n';
        } else if(tip == 2) {
            cin >> a;
            cout << query2(a) << '\n';
        }
    }

    return 0;
}