#include <bits/stdc++.h>
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")

//#define fin cin
//#define fout cout

using namespace std;
using ll = long long;
ifstream fin("aib.in");
ofstream fout("aib.out");
const int nmax = 1e5 + 1;

int n,q;
int aib[nmax];
void update(int pos, int val) {
    for (int i = pos; i <= n; i += i&-i) {
        aib[i] += val;
    }
}
int query(int pos) {
    int ret = 0;
    for (int i = pos; i > 0; i -= i&-i) {
        ret += aib[i];
    }
    return ret;
}
int findK(int s) {
    int st = 1;
    int dr = n;
    int ret = 0;
    while (st <= dr) {
        int mid = ll(st + dr) / 2;
        int val = query(mid);
        if (val > s) {
            dr = mid;
        } else if (val < s) {
            st = mid + 1;
        } else {
            ret = mid;
            break;
        }
    }
    while (query(ret - 1) == s and ret - 1) {
        ret--;
    }
    return ret;
}

int main() {
    fin >> n >> q;
    for (int i = 1; i <= n; i++) {
        int x;
        fin >> x;
        update(i,x);
    }
    while (q--) {
        int t,x,y;
        fin >> t;
        switch (t) {
            case 0:
                fin >> x >> y;
                update(x,y);
                break;
            case 1:
                fin >> x >> y;
                fout << query(y) - query(x - 1) << '\n';
                break;
            default:
                fin >> x;
                fout << findK(x) << '\n';
                break;
        }
    }

    return 0;
}