#include <stdio.h>
#define MAX 100000
int zeros(int x)  {
    return (x ^ (x - 1)) & x;
}
int aib[MAX + 1];
int n, m;

void adauga(int x, int val)  {
    int i;
    for(i = x;i <= n;i += zeros(i))
        aib[i] += val;
}

int calculeaza(int x)  {
    int i, rez = 0;
    for(i = x;i > 0;i-=zeros(i))  {
        rez += aib[i];
    }
    return rez;
}

int cautare(int x)  {
    int st, dr, mijl;
    st = 1;
    dr = n + 1;
    while(dr - st > 1)  {
        mijl = (st + dr) / 2;
        if(calculeaza(mijl) > x)
            dr = mijl;
        else
            st = mijl;
    }
    if(x == calculeaza(st))
        return st;
    return -1;
}
int main()  {
    int i, v, op, a, b;
    FILE *fin = fopen("aib.in", "r");
    fscanf(fin, "%d%d", &n, &m);
    for(i = 1;i <= n;i++)  {
        fscanf(fin, "%d", &v);
        adauga(i, v);
    }
    FILE *fout = fopen("aib.out", "w");
    for(i = 0;i < m;i++)  {
        fscanf(fin, "%d%d", &op, &a);
        if(op == 0)  {
            fscanf(fin, "%d", &b);
            adauga(a, b);
        }
        else if(op == 1)  {
            fscanf(fin, "%d", &b);
            fprintf(fout, "%d\n", calculeaza(b) - calculeaza(a - 1));
        }
        else if(op == 2)  {
            fprintf(fout, "%d\n", cautare(a));
        }
    }
    fclose(fin);
    fclose(fout);
    return 0;
}