#include <cstdio>
#define ub(x) (x&(-x))

using namespace std;

int aib[100010],n,i,m,x,tip,a,b,val;

void update(int x,int i)
 {
    for (int j=i;j<=n;j+=ub(j))
     aib[j]+=x;
 }

int s(int x)
 {
    int rez=0;
    for (int i=x;i>0;i-=ub(i))
        rez+=aib[i];
    return rez;
 }

int cb(int x)
 {
     int st=1,dr=n;
     while (st<=dr)
      {
          int mij=(st+dr)/2;
          if (x==s(mij)) return mij;
          else if (x>s(mij)) st=mij+1;
           else dr=mij-1;
      }
      return -1;
 }

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", &x);
         update(x,i);
     }

    for (i=1;i<=m;++i)
     {
         scanf("%d", &tip);
         if (tip==0)
          {
              scanf("%d %d", &a,&b);
              update(b,a);
          }
          else if (tip==1)
            {
                scanf("%d %d", &a,&b);
                printf("%d\n",s(b)-s(a-1));
            }
            else if (tip==2)
             {
                 scanf("%d", &val);
                 printf("%d\n", cb(val));
             }
     }

    return 0;
}