#include <fstream>

#define lmax 100005
#define bin(x) x&(-x)

using namespace std;

ifstream f("aib.in");
ofstream g("aib.out");

int n,m;

int sum[lmax];

inline void ad(int x,int poz)
{

    for (int i=poz;i<=n;i+=bin(i))
     sum[i]+=x;
}

inline int suma(int poz)
{
   int su=0;

   for (int i=poz;i>=1;i-=bin(i))
    su+=sum[i];

    return su;
}

inline int pozitie(int p)
{
    int st=1,dr=n,m,sum;

    while (st<=dr)
     {
         m=(st+dr)/2;
         sum=suma(m);

         if (sum>p)
          dr=m-1;

         if (sum<p)
          st=m+1;

         if (sum==p)
          return m;
     }

    return -1;
}

int main()
{
    int i,x,y,t,poz;

   f>>n>>m;

   for (i=1;i<=n;i++)
    {
        f>>x;

        ad(x,i);
    }

    for (i=1;i<=m;i++)
     {
         f>>t;

         if (t==0)
          {
              f>>poz>>x;

              ad(x,poz);
          }
         if (t==1)
          {
              f>>x>>y;

              g<<suma(y)-suma(x-1)<<'\n';
          }

         if (t==2)
          {
              f>>x;

              g<<pozitie(x)<<'\n';
          }
     }

   f.close();
   g.close();
}