#include <bits/stdc++.h>

const int inf=2e9;
const int nmax=1e5+3;

using namespace std;

int n,m;
int f[nmax];

int sum(int r)
{
  int l=r-1,res=0;
  while(l>=0)
  {
    res+=f[l];
    l=(l&(l+1))-1;
  }
  return res;
}

void inc(int i,int x)
{
  while(i<n)
  {
    f[i]+=x;
    i=(i|(i+1));
  }
}

int cauta(int x)
{
  int st=0,dr=n;
  while(st<=dr)
  {
    int mid=(st+dr)/2;
    int res=sum(mid);
    if(res>x) dr=mid-1; else
    if(res<x) st=mid+1; else return(mid);
  }
  return -1;
}

int main()
{
  ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
  freopen("aib.in","r",stdin);
  freopen("aib.out","w",stdout);

  cin>>n>>m;
  for(int i=0;i<n;i++)
  {
    int x;
    cin>>x;
    inc(i,x);
  }
  while(m--)
  {
    int k;
    cin>>k;
    if(k==0)
    {
      int i,x;
      cin>>i>>x;
      inc(i-1,x);
    } else
    if(k==1)
    {
      int st,dr;
      cin>>st>>dr;
      cout<<sum(dr)-sum(st-1)<<"\n";
    } else
    if(k==2)
    {
      int x;
      cin>>x;
      cout<<cauta(x)<<"\n";
    }
  }

}