#include <stdio.h>

#define zeros(x) ( (x ^ (x - 1)) & x )

using namespace std;

const int MAXN = 100002;
const int MAXPN = 131072;
int n, m, pn;
int a[MAXN];
int aib[MAXN];

void add(int i, int d) {
    for(; i<=n; i+=zeros(i))
        aib[i] += d;
}

int sumTo(int i) {
    int s;
    for(s=0; i>0; i-=zeros(i))
        s += aib[i];
    return s;
}

int main()
{
    FILE* fin = fopen("aib.in", "r");
    FILE* fout = fopen("aib.out", "w");
    fscanf(fin, "%d %d", &n, &m);
    
    int aaa;
    for(int i=1; i<=n; i++) {
        fscanf(fin, "%d", &aaa);
        add(i, aaa);
    }
    
    int x, xa, xb;
    for(int i=1; i<=m; i++) {
        fscanf(fin, "%d %d", &x, &xa);
        if(x < 2)
            fscanf(fin, "%d", &xb);

        if(x == 0) 
            add(xa, xb);
        if(x == 1)
            fprintf(fout, "%d\n", sumTo(xb) - sumTo(xa-1));
        if(x == 2) {
            int l=1, r=n, mid, val;
            while(l < r) {
                mid = (l+r)/2;
                val = sumTo(mid);
                if(val < xa)
                    l = mid+1;
                else
                    r = mid;
            }
            fprintf(fout, "%d\n", sumTo(l) == xa ? l : -1);
        }
    }
    
    return 0;
}