#include <iostream>
#include <cstdio>
#define fin "aib.in"
#define fou "aib.out"
#define Max 100010
using namespace std;
int n,m,aib[Max];

int minim(int a, int b)
{
    if (a<b) return a;
    else return b;
}

int zeros(int x)
{
    return x^(x-1)&x;
}

void update(int pos,int val)
{
    int i;
    for(i=pos;i<=n;i+=zeros(i)) aib[i]+=val;
}

int query(int poz)
{
    int i,rez=0;
    for(i=poz;i>=1;i-=zeros(i)) rez+=aib[i];
    return rez;
}

int getpos(int val)
{
    int poz=n+1,st=0,dr=n+1,sum,B;
    B=n;
    sum=query(B);
    if(sum==val) poz=n;
    while(st!=dr)
    {
        B=(st+dr)>>1;
        sum=query(B);
        if(sum>val)
        {
            if(dr>B) dr=B;
            B--;
        }
        else if(val==sum) { poz=minim(B,poz); dr=B; B--; }
        else
        {
            if(st<B) st=B;
            B++;
        }
        if(B<=st || B>=dr) break;
    }
    if(poz==n+1) poz=-1;
    return poz;
}
/*int getpos(int Sum)
{
    int pos = n+1, B,S;
    int limst=0, limdr=n+1;

    B = n;
    S = query(B);

    if ( S == Sum ) pos = n;

    while ( B )
    {
          B = (limst+limdr)>>1;
          S = query(B);

          if ( S > Sum )
          {
               if ( limdr > B ) limdr = B;
               B -= 1;
          }
          else if ( S == Sum ) { pos = minim(pos,B), limdr = B, B -= 1; }
          else
          {
              if ( limst < B ) limst = B;
              B += 1;
          }

          if ( B <= limst ) break;
          if ( B >= limdr ) break;
    }

    if ( pos == n+1 ) return -1;
    return pos;
}*/

int main()
{
    int i,x;
    freopen(fin,"r",stdin);
    freopen(fou,"w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&x);
        update(i,x);
    }
    int cod,a,b;
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&cod,&a);
        if(cod!=2) scanf("%d",&b);
        if(cod==0) update(a,b);
        if(cod==1) printf("%d\n",query(b)-query(a-1));
        if(cod==2) printf("%d\n",getpos(a));
    }
    fclose(stdout);
    fclose(stdin);
    return 0;
}