#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

int n,m,c[100001];
int zero(int n)
{
    int a=0;
    while((n & (1<<a))!=(1<<a))a++;
    return a;
}
void actualizare(int poz, int val)
{
c[poz]+=val;
int k=zero(poz);
poz+=(1<<k);
while(poz<=n)
{

   c[poz]+=val;
k=zero(poz);
poz+=(1<<k);

}

}

int interogare(int dr)
{int sum=0;
while(dr)
{
   sum+=c[dr];
   dr=(dr&(dr-1));
}
return sum;
}

int locate(int a,int b,int val)
{
    int m=(a+b)/2;
if(a==b && interogare(m)!=val)return -1;

if(interogare(m)==val)return m;
if(interogare(m)>val)return locate(a,m,val);
return locate(m+1,b,val);
}


int main()
{
    freopen("aib.in","r",stdin);
    freopen("aib.out","w",stdout);
  // freopen("a.in","r",stdin);
  // freopen("a.out","w",stdout);


scanf("%d %d",&n,&m);
int x,y,z;
for(int i=1; i<=n; i++)
{
    scanf("%d ",&z); actualizare(i,z);
}

for(int i=1; i<=m; i++)
{
  scanf("%d ",&x);
  if(x!=2)scanf("%d %d ",&y,&z);else scanf("%d ",&y);
if(x==0)actualizare(y,z);
if(x==1){ if(y==1)printf("%d \n",interogare(z)); else printf("%d \n",interogare(z)-interogare(y-1));   }
if(x==2){ printf("%d \n",locate(1,n,y));}

}
    return 0;
}