#include <fstream>
using namespace std;
ifstream cin("aib.in");
ofstream cout("aib.out");
int aib[100005],n;
void update(int poz,int val)
{
    for( ;poz<=n;poz+=poz^(poz&(poz-1)))
        aib[poz]+=val;
}
int query(int poz)
{
    int sum=0;
    for( ;poz>=1;poz-=poz^(poz&(poz-1)))
        sum+=aib[poz];
    return sum;
}
int bs(int x)
{
    int st,dr,med,ok=-1,s2=0;
    st=1;dr=n;
    while(st<=dr)
    {
        med=(st+dr)/2;
        int s=query(med);
        if(s>=x)
        {
            s2=s;
            ok=med;
            dr=med-1;
        }
        else
            st=med+1;
    }
    if(ok!=-1 && s2!=x)
        ok=-1;
    return ok;
}
int main()
{
    int m,i,a,b,op;
    cin>>n>>m;
    for(i=1;i<=n;i++)
    {
        cin>>a;
        update(i,a);
    }
    for(i=1;i<=m;i++)
    {
        cin>>op>>a;
        if(op!=2)
            cin>>b;
        if(op==0)
            update(a,b);
        if(op==1)
            cout<<query(b)-query(a-1)<<"\n";
        if(op==2)
            cout<<bs(a)<<"\n";
    }
}