#include <cstdio>
#include <cmath>
int n,m,lgn;
int a[100023];
void update(int x,int y)
{
     for(;x<=n;x+=(x&(x^(x-1)))) a[x]+=y;
}
int query(int x)
{
    int s=0;
    for(;x>0;x-=(x&(x^(x-1))))
    {
                              s+=a[x];
    }
    return s;
}
int main()
{
    freopen ("aib.in","r",stdin);
    freopen ("aib.out","w",stdout);
    scanf("%d%d",&n,&m);
    lgn=(int)log2(n);
    for(int i=1;i<=n;i++)
    {
            int nr;
            scanf("%d",&nr);
            update(i,nr);
    }
    for(int i=1;i<=m;i++)
    {
            int tip;
            scanf("%d",&tip);
            if(tip==0)
            {
                      int x1,x2;
                      scanf("%d%d",&x1,&x2);
                      update(x1,x2);
            }
            else if(tip==1)
            {
                 int x1,x2;
                 scanf("%d%d",&x1,&x2);
                 printf("%d\n",query(x2)-query(x1-1));
            }
            else
            {
                int x1;
                scanf("%d",&x1);
                int s=1,e=n,rasp=-1;
                while(s<=e)
                {
                           int mij=(s+e)/2;
                           int val=query(mij);
                           if(val==x1)
                           {
                                      rasp=mij;
                                      e=mij-1;
                           }
                           else if(val<x1) s=mij+1;
                           else e=mij-1;
                }
                printf("%d\n",rasp);
            }
    }
}