#include <cstdio>
#define zeros(x) (((x^(x-1)))&x)

using namespace std;
long  n,m;
int AIB[100002],i,j,k,a,b,c;
void add(int x, int q)
{int i;
    for (i =x;i<=n;i+=zeros(i))
        AIB[i]+=q;
}

int Com(int x)
{
    int i,ret=0;
    for(i=x;i>0;i-=zeros(i))
        ret+=AIB[i];
    return ret;
}
int min(int a)
 {
 int q,i,j,m;
 i=1; j=n;
 while(i<=j)
  {
  m=(i+j)/2;
  q=Com(m);
  if(q == a)
    {
    if(Com(m-1) == a) j=m-1;
    return m;
    }
  else if(q < a) i=m+1;
  else j=m-1;
  }
 return -1;
 }
int main()
{freopen("aib.in","r",stdin);

freopen("aib.out","w",stdout);

scanf("%ld %ld",&n,&m);
for(i=1;i<=n;i++)
{scanf("%d",&k);
add(i,k);
}
for(i=1;i<=m;i++)
{   scanf("%d",&k);
    switch(k)
    {
   case 0:
    {
    scanf("%d %d",&a,&b);
    add(a,b);
    break;
    }
   case 1:
    {
    scanf("%d%d",&a,&b);
    printf("%d\n",Com(b) - Com(a-1));
    break;
    }
   case 2:
    {
     scanf("%d",&a);
     c=min(a);
     printf("%d\n",c);
     break;
    }
   }


}
}