#include <cstdio>
#define nr_zerouri(x) (x ^ (x - 1)) & x
using namespace std;
const int NMAX = 100005;
int v[NMAX];
void actualizare(int poz, int val, int n)
{
    while(poz <= n) {
        v[poz] += val;
        poz += nr_zerouri(poz);
    }
}
int suma(int i)
{
    int sol = 0;
    while(i > 0) {
        sol += v[i];
        i -= nr_zerouri(i);
    }
    return sol;
}
int caut_bin(int val, int n)
{
    int st, dr, mij, sum, last = -1;
    st = 1;
    dr = n;
    while(st <= dr) {
        mij = (st + dr) / 2;
        sum = suma(mij);
        if(sum < val) {
            st = mij + 1;
        }
        else {
            if(sum == val) {
                last = mij;
            }
            dr = mij - 1;
        }
    }
    return last;
}


int main()
{
    int n, m, i, a, b, tip, x;
    freopen("aib.in","r",stdin);
    freopen("aib.out","w",stdout);
    scanf("%d%d", &n, &m);
    for(i = 1;i <= n; ++i) {
        scanf("%d", &x);
        actualizare(i, x, n);
    }
    for(i = 1;i <= m; ++i) {
        scanf("%d%d", &tip, &a);
        if(tip == 0) {
            scanf("%d", &b);
            actualizare(a, b, n);
        }
        else if(tip == 1) {
            scanf("%d", &b);
            printf("%d\n", suma(b) - suma(a - 1));
        }
        else if(tip == 2) {
            printf("%d\n", caut_bin(a, n));
        }
    }
    return 0;
}