#include <bits/stdc++.h>

using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");
int n,m,v[100005],c,a,b,r,i,j,nr,k,avv[100005];
void add(int x, int val)
{
    for(int i=x;i<=n;i += ( i & ( - i ) ))
    v[i]+=val;
}
int sum(int x)
{
    int S=0;
    for(int i=x;i>=1;i-=( i & ( - i ) ))
    S+=v[i];
    return S;
}
int cautare_binara(int n, int r)
{
    int st=1,dr=n,mij;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(sum(mij)>r)dr=mij-1;
        else if(sum(mij)<r)st=mij+1;
        else if(sum(mij)==r)return mij;
    }
    return -1;
}
int main()
{
   f >>n >>m;
   for(i=1;i<=n;i++)
   {
       f>>avv[i];
       add(i,avv[i]);
   }
   for(j=1;j<=m;j++)
   {
       f>>c;
       if(c==0)
       {
           f >>k >>nr;
           add(k,nr);
       }
       else if(c==1)
       {
           f>>a >>b;
           g<<sum(b)-sum(a-1)<<'\n';
       }
       else if(c==2)
       {
           f>>r;
           g<<cautare_binara(n,r)<<'\n';
       }
   }
}