#include <bits/stdc++.h>
#define endl "\n"
#define ll long long
#define ull unsigned long long
using namespace std;

ifstream fin ("aib.in");
ofstream fout("aib.out");
#define cin  fin
#define cout fout

/*
ifstream fin("test.in");
#define cin  fin
*/

int aib[100001];

void adauga(int val, int poz, int n) {
    for(int i=poz; i <= n; i += i & (-i)) {
        aib[i] += val;
    }
}

int query(int x) {
    int sol = 0;
    for(int i=x; i >= 1; i -= i & (-i)) {
        sol += aib[i];
    }
    return sol;
}

int cb(int val, int left, int right) {
    int mid = (left + right) / 2;
    if(aib[mid] == val) {
        return mid;
    }
    if(aib[mid] < val) {
        cb(val, mid + 1, right);
    } else {
        cb(val, left, mid - 1);
    }
}

void solve() {
    int n, q;
    cin >> n >> q;
    for(int i=1; i <=n; i++) {
        int x; cin >> x;
        adauga(x, i, n);
    }

    while(q--) {
        int cerinta; cin >> cerinta;
        if(cerinta == 0) {
            int a, b;
            cin >> a >> b;
            adauga(b, a, n);
        } else if(cerinta == 1) {
            int a, b;
            cin >> a >> b;
            cout << query(b) - query(a-1) << endl;
        } else {
            int sum; cin >> sum;
            cout << cb(sum, 1, n) << endl;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin .tie(0);
    cout.tie(0);

    int testCases = 1;
    //cin >> testCases;
    while(testCases--) {
        solve();
    }
}