#include<fstream>
#include<iostream>
#define DX 100010
using namespace std;
fstream fin("aib.in",ios::in),fout("aib.out",ios::out);

int n,m,aib[DX];
int f(int x)
{
    return (x^(x&(x-1)));
}
void update(int i,int x)
{
    for( ;i<=n;i+=f(i)) aib[i]+=x;
}
int scuipa(int i)
{
    int sum=0;
    for( ;i>0;i-=f(i)) sum+=aib[i];
    return sum;
}
int binary(int pecine)
{
    int st=1,dr=n,m;
    while(st<dr)
    {
        m=(st+dr)/2;
        if(scuipa(m)>=pecine)
            dr=m;
        else
            st=m+1;
    }
    if(scuipa(dr)==pecine)
        return dr;
    else
        return -1;
}
int main()
{
    int a,b,i,x,t;
    fin>>n>>m;
    for(i=1;i<=n;i++)
    {
        fin>>x;
        update(i,x);
    }
    for(i=1;i<=m;i++)
    {
        fin>>t;
        if(t==0)
        {
            fin>>a>>b;
            update(a,b);
        }
        if(t==1)
        {
            fin>>a>>b;
            fout<<scuipa(b)-scuipa(a-1)<<"\n";
        }
        if(t==2)
        {
            fin>>a;
            fout<<binary(a)<<"\n";
        }
    }
}