// 5.09.2009

#include<stdio.h>
int a[100010];
int BIT[100010];
int N;
int dif;
int cc;
int tc;
int P;
int poz;
int Q;

void Update(int P)
{
    while (P <= N)
     {
         BIT[P] += dif;
         P += (P & -P);
     }

}
int Query(int L)
{
    int sum = 0;
    while (L > 0)
     {
         sum += BIT[L];
         L -= (L & -L);
     }
     return sum;
}
int BinSrch(int V)
{
    int st = 1;
    int dr = N;
    poz = -1;
    while (st <= dr)
    {
        int C = Query((st + dr) / 2);

        if (C > V) dr = (st + dr) / 2 - 1;
         else
        if (C < V) st = (st + dr) / 2 + 1;
         else
         {
           poz = (st + dr) / 2;
           break;
         }

    }
    if (poz  != -1)
    {
    while (a[poz] == 0) poz--;
    }
    return poz;

}

int main()
{
    freopen("aib.in","r",stdin);
    freopen("aib.out","w",stdout);

    scanf("%d %d",&N,&tc);
    for(int i = 1; i <= N; i++)
     scanf("%d",&a[i]);
    for(int i = 1; i <= N; i++)
     {
         dif = a[i];
         Update(i);
     }
     for(int i = 1; i <= tc; i++)
      {
          scanf("%d",&cc);
          if (cc == 0)
           {
               scanf("%d %d",&P,&dif);
               a[P] = Q;
               Update(P);
           }
           else
          if (cc == 1)
           {
               scanf("%d %d",&P,&Q);
               int S1 = Query(Q);
               int S2 = Query(P-1);
               printf("%d\n",S1-S2);
           }
           else
          if (cc == 2)
           {
               scanf("%d",&P);
               printf("%d\n",BinSrch(P));
           }
      }
    }