#include <iostream>
#include <stdio.h>
using namespace std;

int aib[100001];
int n,m;


void adauga(int x, int pozitie){
    for(int i=pozitie; i<=n;i+= (i& (-i)))
        aib[i]+=x;

}

int suma ( int pozitie){
    int rez=0;
    for(int i=pozitie;i>0;i-=(i&(-i)))
        rez+=aib[i];

    return rez;
}

int interogare( int numar){
    int st, dr, m;
    st=1; dr=n;
    while(st<=dr){
        m=(st+dr)/2;
        int aux=suma(m);
        if(aux==numar && suma(m-1)<numar){
            return m;
        }
        else if(aux>=numar) dr=m-1;
             else st=m+1;

    }
    return -1;
}


void citire(){

    FILE  * in;
    in=fopen("aib.in","r");
    FILE * out;
    out=fopen("aib.out","w");
    int a,b,c;
    fscanf(in,"%d%d", &n, &m);
    for(int i=1;i<=n;i++){
        fscanf(in,"%d", &a);
        adauga(a, i);
    }

    for(int i=1;i<=m;i++){
        fscanf(in,"%d", &a);
        if(a==0){
            fscanf(in,"%d%d", &b, &c);
            adauga(c, b);
        }
        if(a==1){
            fscanf(in,"%d%d", &b, &c);
            fprintf(out,"%d\n", suma(c)-suma(b-1));
        }
        if(a==2){
            fscanf(in,"%d", &c);
            fprintf(out,"%d\n", interogare(c));
        }

    }

}


int main()
{
    citire();
    return 0;
}