#include <iostream>
#include <fstream>
using namespace std;

ifstream fin ("aib.in");
ofstream fout ("aib.out");

const int maxN = 1e5;

int bit[maxN], v[maxN];
int n;

int add(int a, int b) {
    for(a; a <= n; a += a & -a)
        bit[a] += b;
}

int suma(int dr) {
    int ans = 0;
    for(dr; dr > 0; dr -= dr & -dr)
        ans += bit[dr];
    return ans;
}

int sum(int st, int dr) {
    return suma(dr) - suma(st-1);
}

int main()
{
    int m; fin >> n >> m;
    for(int i = 1; i <= n; ++i) {
        int x; fin >> x;
        add(i, x);
    }
    for(int i = 1; i <= m; ++i) {
        int x, a, b; fin >> x;
        if(x == 0) {
            fin >> a >> b;
            add(a, b);
        }
        if(x == 1) {
            fin >> a >> b;
            fout << sum(a, b) << "\n";
        }
        if(x == 2) {
            fin >> a;
            int poz = -1, st = 1, dr = n;
            while(st <= dr) {
                int mij = (st+dr) / 2;
                int val = sum(1, mij);
                if(val == a)
                    poz = mij;
                if(val < a)
                    st = mij + 1;
                else
                    dr = mij - 1;
            }
            fout << poz << "\n";
        }

    }
    return 0;
}