#include <stdio.h>

FILE *in = fopen("aib.in", "r");
FILE *out= fopen("aib.out","w");

#define MAXN 100005

int m, n, vec[2 * MAXN];
//vectorul reprezinta un ARBORE BINAR DE INTERVALE
//vec[1] -> intervalul [1, n];
//intervalele sunt de forma [2 ^ k, 2 ^ q] sau [2 ^ k, n] (daca este unul din intervalele capat dreapta)
//frunzele sunt elementele vectorului in sine
//restul cuprind suma frunzelor descendente
int nivelMax; //utilizat pt a ajunge din nodul X la cel din dreapta sa

int cautaSum1(int val)
{
    int st = 1, dr = n;
    int nod = 1;
    int nivel = nivelMax;
    int sum = 0;
    //cam aceeasi metoda ca la adaugare in parcurgerea arborelui
    if(val > vec[1])
        return -1;
    
    while(sum != val && st < dr)
    {
        if(sum + vec[nod + 1] >= val)
        //punctul cautat se afla in intervalul stang
        {
            if(st + nivel - 1 <= n)
                dr = st + nivel - 1;
            nod++;
        }
        else
        //dreapta se afla in intervalul drept => [1, dreapta] cuprinde intevalul stang
        {
            sum += vec[nod + 1];
            st  += nivel;
            nod += nivel * 2;
        }
        if(sum + vec[nod] == val)
            return dr;
        nivel >>= 1;
    }
    return -1;
}

int sum1(int indice)
//calculeaza suma elementelor din [1, indice]
{
    if(indice == 0)
        return 0;
        
    int st = 1, dr = n;
    int nod = 1;
    int nivel = nivelMax;
    int sum = 0;
    //cam aceeasi metoda ca la adaugare in parcurgerea arborelui
    //doar ca trebuie oprit cand capatul drept al intervalului e egal cu indicele
    
    while(dr != indice)
    {
        if(indice <= st + nivel - 1)
        //dreapta se afla in intervalul stang
        {
            if(st + nivel - 1 <= n)
                dr = st + nivel - 1;
            nod++;
        }
        else
        //dreapta se afla in intervalul drept => [1, dreapta] cuprinde intevalul stang
        {
            sum += vec[nod + 1];
            st  += nivel;
            nod += nivel * 2;
        }
        nivel /= 2;
    }
    sum += vec[nod];
    return sum;
}

inline int sum(int stanga, int dreapta)
//returneaza suma elementelor dintre st si dr
{
    //se calculeaza sum[1, dreapta] - sum[1, stanga - 1]
    return sum1(dreapta) - sum1(stanga - 1);
}

void adauga(int indice, int valoare)
{
    int st = 1, dr = n;
    int nod = 1;
    int nivel = nivelMax;
    vec[1] += valoare;
    //se cauta in arbore indicele si se adauga la toate intervalele care il cuprind valoarea

    while(st < dr)
    {
        if(indice <= st + nivel - 1)
        //indicele se afla in intervalul din stanga
        {
            if(st + nivel - 1 <= n)
                dr = st + nivel - 1;
            nod++;
        }
        else
        //indicele se afla in intervalul din dreapta
        {
            st  += nivel;
            nod += nivel * 2;
        }
        nivel /= 2;
        vec[nod] += valoare; //intervalul din `nod` cuprinde indicele
    }
}

int main()
{
    fscanf(in, "%i %i", &n, &m);
    
    int i, x, a, b, op;
    for(nivelMax = 1 << 30; !(nivelMax & n); nivelMax >>= 1);
    for(i = 1; i <= n; i++)
    {
        fscanf(in, "%i", &x);
        adauga(i,x);
    }
    for(i = 1; i <= m; i++)
    {
        fscanf(in, "%i", &op);
        switch(op)
        {
        case 0:
            fscanf(in, "%i %i", &a, &b);
            adauga(a, b);
            break;
        case 1:
            fscanf(in, "%i %i", &a, &b);
            fprintf(out, "%i\n", sum(a, b));
            break;
        case 2:
            fscanf(in, "%i", &a);
            fprintf(out, "%i\n", cautaSum1(a));
            break;
        }
    }
}