#include <bits/stdc++.h>
#define NMAX 15005
#define zeros(x) ( (x ^ (x - 1)) & x )
using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");

int n,m;
int v[NMAX];
int aib[NMAX];

void citire();
void add(int poz,int val);
void rezolvare();
int sum(int x);
int cautare(int x);
int main()
{citire();
 rezolvare();
 return 0;
}
void citire()
{int i;
 fin>>n>>m;
 for(i=1;i<=n;i++)
     {fin>>v[i];
      add(i,v[i]);
     }
}
void add(int poz,int val)
{int i;
 for(i=poz;i<=n;i+=zeros(i))
    aib[i]+=val;
}
void rezolvare()
{int i,cer,x,y;
 for(i=1;i<=m;i++)
    {fin>>cer;
     if(cer==0)
        {fin>>x>>y;
         add(x,y);
        }
        else
            if(cer==1)
              {fin>>x>>y;
               fout<<sum(y)-sum(x-1)<<'\n';
              }
              else
                {fin>>x;
                 fout<<cautare(x)<<'\n';
                }
    }
}
int sum(int x)
{int i,cat=0;
 for(i=x;i>0;i-=zeros(i))
     cat+=aib[i];
 return cat;
}
int cautare(int x)
{int st,dr,mij=0;
 st=0;
 dr=n+1;
 while(st+1<dr)
      {mij=(st+dr)/2;
       if(sum(mij)<x)
        st=mij;
        else
            dr=mij;
      }
 if(sum(dr)==x)
    return dr;
    else
      return -1;
}