//******************************************************
//vector V cu N element natural.  M operatii astfel :
//  0 a b - v[a] = v[a] + b.
//  1 a b - SUM[a,b].
//  2 a - K minim where SUM[k,2K] = a
//*************************************************************************

#include <iostream>
#include <fstream>
#include <vector>
#include <string.h>

using namespace std;

const int nmax = 100001 ;
const int mmax = 150001 ;
int v[nmax] ;
int n;

//  1. 2's complement
//  2. AND with original
//  3. SUB from original
inline int getFather(int a){
    return a - (a & -a);
}

//  1. 2's complement
//  2. AND with original
//  3. ADD from original
inline int getNext(int a){
    return a + (a & -a);
}

void update(int ind, int val) {
    v[ind] = v[ind] + val;
    ind = getNext(ind);
    if (ind <= n ) update(ind,val);
}

int sum(int a, int b) {
    unsigned int suma = 0;
    while (b > 0) {
        suma += v[b];
        b = getFather(b);
    }
    while (a > 0) {
        suma -= v[a];
        a = getFather(a);
    }
    return (int)suma ;
}

int index(int a) {
    int k = n,el = 0, ve = n+1, s;
    s = sum(0,k);
    if (s == a) return k;

    while (el <= ve) {
        int k = (el + ve) / 2 ;
        s = sum(0,k);
        if (s < a)          el = k+1;
        else if (s == a)    return k;
        else                ve = k-1;
    }
    if (s == a) return k ;
    return -1;
}


int index2(int a) {
    int rez = 0;
    for(int pas=1<<18;pas;pas>>=1)
        if(rez+pas<=n&&sum(0,rez+pas)<a)
            rez+=pas;
    if(sum(0,rez+1)==a)
       return rez + 1 ;
    return -1;
}
int main()
{
    int x,m,a,b;
    freopen("aib.in","r",stdin);
	freopen("aib.out","w",stdout);
    scanf("%d %d",&n, &m);
    memset(v,0,4*(n+1));

    for(int i = 1; i<=n; i++) {
        scanf("%d",&x);
        update(i,x);
    }

    for(int i = 0; i< m ; i++) {
        scanf("%d",&x);
        if (x == 0) {
            scanf("%d %d",&a ,&b);
            update(a,b);
        }
        else if (x == 1 ) {
            scanf("%d %d",&a ,&b);
            printf("%d\n",sum(a-1,b));
        }
        else {
            scanf("%d",&a);
            printf("%d\n",index2(a));
        }
    }
    return 0;
}