#include <iostream>
#include <cstdio>
using namespace std;
FILE *f=fopen("aib.in","r");
int a[150000],aib[150000],n,m;
FILE *f1=fopen("aib.out","w");
int zero(int x)
{
    return (x^(x-1))&x;
}
void inserare(int i,int x)
{
    for(int j=i;j<=n;j+=zero(j))
       aib[j]+=x;

}
int suma(int i)
{
   int s=0;
   while(i)
   {
       s+=aib[i];
       i=i-zero(i);
   }
   return s;
}
int caut(int x)
{
    int s = 1, d = n;

    while(s <= d)
    {
        int mij = (s + d) / 2;


        if(suma(mij) == x)
        {
            return mij;
        }
        else if(suma(mij)> x)
            d = mij - 1;
        else
            s = mij + 1;
    }

    return -1;
}
void citire( )
{
    fscanf(f,"%d%d",&n,&m);
    int r;
    for(int i=1;i<=n;i++)
        {
            fscanf(f,"%d",&a[i]);
            inserare(i,a[i]);
        }

    for(int i=1;i<=m;i++)
    {
        fscanf(f,"%d",&r);
        int x1,x2;
        if(r==0)
        {
            fscanf(f,"%d%d",&x1,&x2);
            inserare(x1,x2);
        }
        else
            if(r==1)
             {
            fscanf(f,"%d%d",&x1,&x2);
            fprintf(f1,"%d\n",suma(x2) - suma(x1-1));

        }
         else
            if(r==2)
             {
            fscanf(f,"%d",&x1);
            fprintf(f1,"%d\n",caut(x1));

             }
    }
}


int main()
{
    citire();


    return 0;
}