#include <bits/stdc++.h>
#define zeros(x) ((x)&(-x))
using namespace std;

int n,h,m, aib[10002];

void add(int x, int q)
{
    int i;
    for(i=x;i<=n;i+=zeros(i));
    aib[i]+=q;
}

int compute(int x)
{
    int i, r=0;
    for(int i=0;i>0;i-=zeros(i))
        r+=aib[i];
    return r;
}

int cautbinar(int st, int dr, int k)
{ int mij;
    if(compute(st)==k) return st;
    if(compute(dr)==k) return dr;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(compute(mij)==k) return mij;
        if(compute(mij)<k) mij+=1;
        if(compute(mij)>k) mij-=1;
    }
    return -1;


}

int i,x,y,z;

int main()
{
    freopen("aib.in", "r", stdin);
    freopen ("aib.out", "w", stdout);
     scanf("%d %d", &n, &m);
     for(i=1;i<=n;i++)
        scanf ("%d", &h);
        add(i,h);
     for(i=1;i<=m;i++)
     {
         scanf("%d", &z);

         if(z==0)
         {
             scanf("%d %d", &x, &y);
             add(x,y);
         }
         if(z==1)
         {
             scanf("%d %d", &x, &y);
             printf("%d\n",compute(y)-compute(x-1));
         }
         if(z==2)
         {
             scanf ("%d", &x);
             printf("%d", cautbinar(1,n,x));
         }

     }






    return 0;
}