#include <iostream>
#include <fstream>
#include <cstdio>
#include <cstring>
#define NMax 100001
using namespace std;
ifstream g("aib.in");
ofstream f("aib.out");

void Update(int *AIB,int M,int Index,int Valoare)
{
    for(;Index<=M;Index=Index + (Index & (-Index)))
        AIB[Index]+=Valoare;
}

int Query(int *AIB,int index)
{
    int Suma,iterator;
    for(Suma=0,iterator=index;iterator>0;iterator-=iterator & (-iterator))
        Suma+=AIB[iterator];
    return Suma;
}

int search(int *AIB, int position1, int M, int MaxIndex, int valoare)
{
    int step, i, Suma = 0;

    for (i = 0, step = MaxIndex; step; step >>= 1)
        if (i + step <= M && AIB[i + step] <= valoare) {
            i += step;
            valoare -= AIB[i];

            if (!valoare)
                return i;
        }

    return -1;
}

int BruteForceSearch(int *AIB,int M,int valoare)
{
    for(int iterator=1;iterator<=M;++iterator)
        if(Query(AIB,iterator)==valoare)
        return iterator-1;
    return -1;
}

int main()
{
    int MaxIndex;
    int Arbore_Indexat_Binar[NMax],N,M,operatie,a,b;
    //freopen("aib.in", "r", stdin);
    //freopen("aib.out","w", stdout);

    ///INITIALIZARE STRUCTURA:
///____________________________________________________________________________________________________________________________________

    memset(Arbore_Indexat_Binar, 0, sizeof(Arbore_Indexat_Binar));
    ///CITIREA ELEMENTELOR:
///____________________________________________________________________________________________________________________________________

     g>>M>>N;
   // scanf("%d %d\n", &M, &N);
    for(int i=1;i<=M;++i)
    {
        //scanf("%d",&a);
        g>>a;
        Update(Arbore_Indexat_Binar,M,i,a);
    }
    for(MaxIndex = 1; MaxIndex < M ;MaxIndex <<= 1);

    ///RASPUND LA FIECARE OPERATIE:
///_______________________________________________________________________________________________________________________________________
    for(;N;--N)
    {
        //scanf("%d %d", &operatie, &a);
        g>>operatie>>a;
        switch(operatie)
        {
            case 0:
                //scanf("%d", &b);
                g>>b;
                Update(Arbore_Indexat_Binar,M,a,b);
                break;
            case 1:
                //scanf("%d", &b);
                g>>b;
                //printf("%d\n",Query(Arbore_Indexat_Binar,b)-Query(Arbore_Indexat_Binar,a-1));
                f<<Query(Arbore_Indexat_Binar,b)-Query(Arbore_Indexat_Binar,a-1)<<"\n";
                break;
            case 2:
                //printf("%d\n", BruteForceSearch(Arbore_Indexat_Binar,M,b));
                //g>>a;
                f<<search(Arbore_Indexat_Binar,1,M,MaxIndex,a)<<"\n";
                break;
            default: break;
        }
    }
///________________________________________________________________________________________________________________________________________
}