#include <iostream>
#include <fstream>
#define lsb(x) ((-x)&x)
using namespace std;
int arb[100005],n,m;
inline void actualizare(int valoare,int pozitie)
{
    for(int ii=pozitie; ii<=n; ii+=lsb(ii))
    {
        arb[ii]+=valoare;
    }
}
inline int calculez(int pozitie)
{
    int suma=0;
   while(pozitie )
        {suma+=arb[pozitie];
        pozitie-=lsb(pozitie);
        }
    return suma;
}
inline int dif(int poz1,int poz2)
{
    return (calculez(poz2)-calculez(poz1-1));
}
inline int instr2(int val)
{
    int st=1,dr=n,mij,poz=-1;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(calculez(mij)==val)
        {
            return mij;
        }
        else if(calculez(mij)>val)
        {
            dr=mij-1;
        }
        else st=mij+1;
    }
    return -1;
}
int main()
{
    FILE *f;
    FILE *g;
    f=fopen("aib.in","r");
    g=fopen("aib.out","w");
    fscanf(f,"%d %d",&n,&m);
    for(int i=1; i<=n; i++)
    {
        int val;
        fscanf(f,"%d",&val);
        actualizare(val,i);
    }
    while(m)
    {
        int instr;
         fscanf(f,"%d",&instr);
        m--;
        if(instr==0)
        {
            int a,b;
            fscanf(f,"%d %d",&a,&b);
            actualizare(b,a);
        }
        else if(instr==1)
        {
            int a,b;
            fscanf(f,"%d %d",&a,&b);
            fprintf(g,"%d \n",dif(a,b));
        }
        else
        {
            int a;
            fscanf(f,"%d",&a);
            fprintf(g,"%d \n",instr2(a));
        }
    }
    return 0;
}