#include <bits/stdc++.h>
using namespace std;
#define cin fi
#define cout fo

ifstream fi("aib.in");
ofstream fo("aib.out");
int n, m, q, x;
int a, b;
bool found;

int aib[100005];
int p2[20] = {1}, mp, p;

void update(int, int);
void create();
int query(int);
void solve();

int main(){

    cin >> n >> m;
    create();
    for (int i = 0; i < m; ++i){solve();}

    return 0;
}



void update(int i, int x){

    for (int j = i; j <= n; j += (j & -j)){

        aib[j] += x;
    }
}

int query(int i){

    int sum = 0;

    for (int j = i; j >= 1; j -= (j & -j)){

        sum += aib[j];
    }

    return sum;
}

void solve(){

    cin >> q;
    if (q == 0) {

        cin >> a >> b;
        update(a, b);
    }
    else if (q == 1) {

        cin >> a >> b;
        cout << query(b) - query(a - 1) << '\n';
    }
    else {

        cin >> a;
        p = mp;
        found = false;
        while (!found) {

            b = query(p2[p - 1]);
            if (b == a) {

                found = true;
                cout << p2[p - 1] << '\n';
            }
            else if (b > a) {

                p /= 2;
            }
            else {

                for (b = mp - 1; p2[p - 1] + p2[b - 1] > n; --b){b = b;}
                p += b;
            }
        }
    }
}

void create() {

    for (int i = 1; i <= n; ++i) {

        cin >> x;
        update(i, x);
    }

    for (int i = 1; i <= n; ++i) {

        p2[i] = p2[i - 1] * 2;
        if (p2[i] <= n) {

            mp = i;
        }
    }
}