#include <bits/stdc++.h>
using namespace std;

const int L = 16;

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

long long query(int i, vector<int>& aib) {
    long long sum=0;
    while (i>0) {
        sum+=aib[i];
        int p2=i&(-i);
        i-=p2;
    }
    return sum;
}

int search(int val, int n, vector<int>& aib) {
    int i=0, pas=1<<L;
    int copie_val=val;
    while (pas!=0) {
        if (i+pas <= n && aib[i+pas] < val) {
            i+=pas;
            val-=aib[i];
        }
        pas/=2;
    }

    if (query(i+1, aib) == copie_val) {
        return i+1;
    }

    return -1;
}

int main()
{
    ifstream f("aib.in");
    ofstream g("aib.out");
    int n,m; f >> n >> m;
    vector<int> v(n+1);
    vector<int> aib(n+1);

    for (int i=1;i<=n;i++) {
        f >> v[i];
        update(i, v[i], n, aib);
    }

    for (int i=0;i<m;i++) {
        int tip; f >> tip;

        if (tip==1) {
            int st, dr;
            f >> st >> dr;
            g << query(dr, aib) - query(st-1, aib) << '\n';
        } else if (tip==2) {
            int val; f >> val;
            g << search(val, n, aib) << '\n';
        } else if (tip==0) {
            int poz, val;
            f >> poz >> val;
            update(poz, val, n, aib);
        }
    }

    f.close();
    g.close();

    return 0;
}