#include <fstream>
#include <set>
#include <vector>
using namespace std;

ifstream cin("aib.out");
ofstream cout("aib.in");

struct AIB {

    vector<int> aib;
    int n;

    AIB() {

    }

    AIB(int size) {

        n = size + 1;
        aib.resize(n);

    }

    void add(int x,int i) {

        while (i <= n) {
            aib[i] += x;
            i += i & -i;
        }

    }

    int query(int i) {

        int sum = 0;

        while (i > 0) {
            sum += aib[i];
            i -= i & -i;
        }

        return sum;

    }

    int rangesum(int i1,int i2) {

        return query(i2) - query(i1-1);

    }


};

AIB aib;

int main() {

    int n,q;
    cin>>n>>q;

    aib = AIB(n);

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

        int x;
        cin>>x;

        aib.add(x,i);

    }

    for (int i=0; i<q; i++) {

        int c,a,b;

        cin>>c;

        if (c == 0) {
            cin>>a>>b;

            aib.add(b,a);

        }

        if (c == 1) {

            cin>>a>>b;

            cout<<aib.rangesum(a,b)<<"\n";

        }

        if (c == 2) {

            cin>>a;

            int l=1,r=n;

            while (l <= r) {
                int mid = (l + r) / 2;

                int x = aib.query(mid);

                if (x == a) {
                    cout<<mid<<"\n";
                    break;
                }
                else if (x > a) {
                    r = mid;
                }
                else {
                    l = mid+1;
                }

            }


        }

    }

}