#include <fstream>
#include <vector>
#define int long long

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

struct AIB {
    std::vector<int> v;
    size_t n;

    AIB() = default;
    AIB(size_t n) {
        this->n = n;
        v.resize(n+1);
    }

    void add(int x,size_t i) {
        while (i <= n) {
            v[i] += x;
            i += i & -i;
        }
    }

    int sum(int i) {
        int rez = 0;
        while (i > 0) {
            rez += v[i];
            i -= i & -i;
        }
        return rez;
    }

    int rangesum(int i1, int i2) {
        return sum(i2) - sum(i1-1);
    }
};

signed main() {
    int n,m;
    cin>>n>>m;
    AIB aib(n);  

    for (int i=1; i<=n; i++) {
        int x;
        cin>>x;
        aib.add(x,i);
    }

    for (int i=1; i<=m; i++) {
        int c;
        cin>>c;

        if (c == 0) {
            int a,b;
            cin>>a>>b;
            aib.add(b,a);
        }
        else if (c == 1) {
            int a,b;
            cin>>a>>b;
            cout<<aib.rangesum(a,b)<<"\n";
        }
        else {
            int a;
            cin>>a;

            int l=1,r=n,rez = 0,rezp = 0;
            while (l <= r) {
                int mid = (l + r)/2;

                int x = aib.sum(mid);

                if (x < a) {
                    l = mid+1;
                }
                else {
                    rez = x;
                    rezp = mid;
                    r = mid-1;
                }
            }

            if (rez == a) cout<<rezp<<"\n";
            else cout<<"-1\n";
        }
    }
}