#include <stdio.h>

using namespace std;
FILE *f,*g;
int N,M, AIB[10010];
void CreateAIB(int X,int P)
{
    for(;P<=N;P+=(P&(-P)))AIB[P]+=X;///formez arborii de sume
}
void Read()
{
    int i,X;
    fscanf(f,"%d %d",&N,&M);
    for(i=1;i<=N;i++)
    {
        fscanf(f,"%d",&X);
        CreateAIB(X,i);
    }
}
int SUM(int X)
{
    int Sum=0;
    for(;X>0;X-=(X&(-X)))
        Sum+=AIB[X];
    return Sum;
}
int SearchK(int A)
{
    int Left=1,Right=N,Middle,s;
    while(Left<=Right)
    {
        Middle=(Left+Right)/2;
        s=SUM(Middle);
        if(s==A)
            return Middle;
        else
            if(s>A)Right=Middle-1;
            else
                Left=Middle+1;
    }
    return -1;
}
void Solve()
{
    int i,A,B,operation;
    while(M)
    {
        M--;
        fscanf(f,"%d",&operation);
        if(!operation)
        {
            fscanf(f,"%d %d",&A,&B);
            CreateAIB(B,A);
            continue;
        }
        if(operation==1)
        {
            fscanf(f,"%d %d",&A,&B);
            fprintf(g,"%d\n",SUM(B)-SUM(A-1));///calculze suma din intervalul [1,B], apoi scad suma [1,A-1]
            continue;
        }
        if(operation==2)
        {
            fscanf(f,"%d",&A);
            fprintf(g,"%d\n",SearchK(A));
        }
    }
}
int main()
{
    f=fopen("aib.in","r");g=fopen("aib.out","w");
    Read();
    Solve();
    fclose(f),fclose(g);
    return 0;
}