#include <bits/stdc++.h>

using namespace std;

ifstream f("aib.in");
ofstream g("aib.out");
int AIB[100005],n,m;
void Update(int x1,int x)
{
    for(int i=x1; i<=n; i+=i^(i-1)&i)
        AIB[i]+=x;
}
int Query(int x)
{
    int rez=0;
    for(int i=x; i; i-=i^(i-1)&i)
        rez+=AIB[i];
    return rez;
}
int main()
{
    f>>n>>m;
    for(int i=1; i<=n; i++)
    {
        int x;
        f>>x;
        Update(i,x);
    }
    while(m--)
    {
        int x,y,cer;
        f>>cer;
        assert(cer==0||cer==1||cer==2);
        if(!cer)
            f>>x>>y,Update(x,y);
        else if(cer==1)
            f>>x>>y,g<<Query(y)-Query(x-1)<<'\n';
        else
        {
            f>>x;
            int st=1,dr=n,poz=-1;
            while(st<=dr&&poz==-1)
            {
                int mi=(st+dr)>>1;
                if(Query(mi)==x)
                    poz=mi;
                else if(Query(mi)<x)
                    st=mi+1;
                else
                    dr=mi-1;
            }
            g<<poz<<'\n';
        }
    }

    return 0;
}