#include <cstdio>
#define MAX_N 100000
using namespace std;

int n, aib[MAX_N+5];
inline int lsb(int x){
    return ((x^(x-1))&x);
}
void update(int p, int nr){
    while (p<=n){
        aib[p]+=nr;
        p+=lsb(p);
    }
}

int sum(int p){
    int s=0;
    while (p>=1){
        s+=aib[p];
        p-=lsb(p);
    }
    return s;
}

int binarySearch(int st, int dr, int val){
    int mid, a;
    while (st<=dr){
        mid=(st+dr)/2;
        a=sum(mid);
        if (a==val)
            return mid;
        if (a<val)
            st=mid+1;
        else dr=mid-1;
    }
    return -1;
}

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