#include <iostream>
#include <fstream>
using namespace std;
int n,m;
int i;
int aid[100001];
void update(int p,int s)
{
    while (p<=n)
    {
        aid[p]+=s;
        p=p+(p&(-p));
    }
}
int querry(int x)
{
    int suma=0;
    while (x>0)
    {
        suma+=aid[x];
        x-=x&(-x);
    }
    return suma;
}
    int b=1;
ofstream out("aib.out");
int cautbin(int s)
{
int mij,p = -1,st=1, dr=n;
int suma;
    while (st<=dr)
    {
        mij=(st+dr)/2;
        suma=querry(mij);
    if (suma>=s)
     {
       if (suma==s) p=mij;
       dr=mij-1;
     }
    else st=mij+1;
    }
    return p;
}

int main()
{
    ifstream in("aib.in");

    in>>n>>m;
    int x;
    for (i=1;i<=n;i++)
    {
        in>>x;
        update(i,x);
    }
    int s;
    int tip,y,p;
    for (i=1;i<=m;i++)
    {
        in>>tip;
        if (tip==0)
        {
            in>>p>>s;
            update(p,s);
        }
        if (tip==1)
        {
            in>>x>>y;
            out<<querry(y)-querry(x-1)<<"\n";
        }
        if (tip==2)
        {
            in>>x;
           out<<cautbin(x)<<"\n";
        }
    }
    out.close();
    in.close();
    return 0;
}