#include <iostream>
#include<fstream>
using namespace std;

ifstream fin("aib.in");
ofstream fout("aib.out");
int aib[100000];
const int INF=2e9;
int n, m;
void update(int x, int y)
{
    for(int i=x; i<=n; i+=(i&(-i)))
    {
        aib[i]+=y;
    }
}
int query(int x)
{
    int s=0;
    for(int i=x; i>=1; i-=(i&(-i)))
    {
        s=s+aib[i];
    }
    return s;
}
int cbin(int x)
{
    int pas, cs, ans;
    ans=0;
    pas=1<<17;
    cs=0;
    while(pas)
    {
        if(ans+pas<=n && cs+aib[ans+pas]<=x)
        {
            cs+=aib[ans+pas];
            ans+=pas;
            if(cs==x)
            {
                return ans;
            }
        }
        pas>>=1;
    }

    return -1;
}

int main()
{
    int nr, x, y, t;
    fin>>n>>m;
    for(int j=1; j<=n; j++)
    {
        fin>>nr;
        update(j, nr);
    }
    for(int j=1; j<=m; j++)
    {
        fin>>t>>x;
        if(t!=2)
        {
            fin>>y;
        }
        if(t==0)
        {
            update(x, y);
        }
        else if(t==1)
        {
            fout<<query(y)-query(x-1)<<"\n";;
        }
        else
        {
            fout<<cbin(x)<<"\n";
        }

    }

    return 0;
}