#include <bits/stdc++.h>
using namespace std;

ifstream fin("aib.in");
ofstream fout("aib.out");


class Aib
{
private:
    int *aib,n;
public:
    Aib(int _n)
    {
        n=_n;
        aib=new int[n];
        for(int i=1;i<=n;i++)
            aib[i]=0;
    }

    Aib(int a[],int _n,int op)
    {
        n=_n;
        aib=new int[n];
        for(int i=1;i<=n;i++)
            aib[i]=a[i];
        if(op==2)
        {
            int i,k;
            for(i=1;i<n;i++)
            {
                k=i+(i&(-i));
                if(k<=n)
                    aib[k]+=aib[i];
            }
        }
        else if(op==3)
        {
            int i,k;
            for(i=1;i<n;i++)
            {
                k=i+(i&(-i));
                if(k<=n)
                    aib[k]*=aib[i];
            }
        }
    }

    ~Aib()
    {
        n=0;
        delete[] aib;
    }

    void UpdateS(int k,int val)
    {
        while(k<=n)
        {
            aib[k]+=val;
            k=k+(k&(-k));
        }
    }

    void UpdateM(int k,int val)
    {
        while(k<=n)
        {
            aib[k]*=val;
            k=k+(k&(-k));
        }
    }

    int QueryS(int k)
    {
        int s=0;
        while(k>=1)
        {
            s+=aib[k];
            k-=(k&(-k));
        }
        return s;
    }

    int QueryM(int k)
    {
        int p=1;
        while(k>=1)
        {
            p*=aib[k];
            k-=(k&(-k));
        }
        return p;
    }

    int Cautbin(int x)/// pusa la misto de dragul problemei
    {
        int st=1,dr=n,mij,poz=-1;
        while(st<=dr)
        {
            mij=(st+dr)/2;
            if(QueryS(mij)>=x)
            {
                dr=mij-1;
                poz=mij;
            }
            else st=mij+1;
        }
        if(QueryS(poz)==x)return poz;
        return -1;
    }
};

void Manevra1()
{
    int n,i,k;
    cin>>n;
    Aib a(n);
    for(i=1;i<=n;i++)
    {
        cin>>k;
        cout<<a.QueryS(k)<< " ";
        a.UpdateS(k,1);
    }
    return;
}




void Manevra2()
{
    int n,m,i,op,x,y;
    fin>>n>>m;
    int ar[n+1];
    for(i=1;i<=n;i++)
        fin>>ar[i];
    Aib a(ar,n,2);
    for(i=1;i<=m;i++)
    {
        fin>>op;
        if(op==0)
        {
            fin>>x>>y;
            a.UpdateS(x,y);
        }
        if(op==1)
        {
            fin>>x>>y;
            fout<<a.QueryS(y)-a.QueryS(x-1)<<"\n";
        }
        if(op==2)
        {
            fin>>x;
            fout<<a.Cautbin(x)<<"\n";
        }
    }
}

int main()
{
    Manevra2();
    return 0;
}