#include<bits/stdc++.h>
using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");
const int N = 100010;
int n,m,t,a,b,aib[N];
int suma(int p)
{
    int ret=0;
    for(;p;p-=p&(-p))
        ret+=aib[p];
    return ret;
}
void upd(int p,int val)
{
    for(;p<=n;p+=p&(-p))
        aib[p]+=val;
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int x;
        f>>x;
        upd(i,x);
    }
    for(;m;m--)
    {
        f>>t>>a;
        if(t==0)
        {
            f>>b;
            upd(a,b);
            continue;
        }
        if(t==1)
        {
            f>>b;
            g<<suma(b)-suma(a-1)<<'\n';
            continue;
        }
        int st=0,dr=n,mi;
        while(dr-st>1)
        {
            mi=(st+dr)/2;
            if(suma(mi)<a)
                st=mi;
            else
                dr=mi;
        }
        if(suma(dr)!=a)
            dr=-1;
        g<<dr<<'\n';
    }
    return 0;
}