#include <fstream>
using namespace std;
ifstream in("aib.in");
ofstream out("aib.out");
int lsb(int x)
{
    return x&-x;
}
int n,aib[100001];
void upd(int poz,int val)
{
    for(; poz<=n; poz+=lsb(poz))
        aib[poz]+=val;
}
int ans(int poz)
{
    int sum=0;
    for(; poz>0; poz-=lsb(poz))
        sum+=aib[poz];
    return sum;
}
int cautbin(int poz)
{
    int r=0,pas=1<<16,sum=0;
    while(pas)
    {
        if(r+pas<=n&&sum+aib[r+pas]<=poz)
        {
            r+=pas;
            sum+=aib[r];
        }
        pas/=2;
    }
    if(sum==poz)
        return r;
    else
        return -1;
}
int main()
{
    int m,i,a,b,t;
    in>>n>>m;
    for(i=1; i<=n; i++)
    {
        in>>a;
        upd(i,a);
    }
    for(i=1; i<=m; i++)
    {
        in>>t;
        if(t==0)
        {
            in>>a>>b;
            upd(a,b);
        }
        else if(t==1)
        {
            in>>a>>b;
            out<<ans(b)-ans(a-1)<<'\n';
        }
        else
        {
            in>>a;
            out<<cautbin(a)<<'\n';;
        }
    }
    return 0;
}