#include <bits/stdc++.h>
#define Dim 100005
using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");
long N,M,a,aib[Dim],p,b,c,d;

void Update(int poz)
{
    do
    {
        aib[poz]+=a;
        poz+=poz & -poz;

    }while(poz<=N);
}

long SUM(int poz)
{
    long s=0;
    while(poz)
    {
        s+=aib[poz];
        poz&=poz-1;
    }
    return s;
}

int main()
{
    f>>N>>M;
    for(int i=1;i<=N;i++)
    {
        f>>a;
        Update(i);
    }
    for(int i=1;i<=M;i++)
    {
        f>>p;
        if(p==0)
        {
            f>>c>>a;
            Update(c);
        }
        else
        if(p==1)
        {
            f>>a>>b;
            g<<SUM(b)-SUM(a-1)<<'\n';
        }
        else
        {
            f>>a;
            int st=1,dr=N;
            bool stop=1;
            while(st<=dr&&stop==1)
            {
                int mij=(st+dr)/2;
                long calc=SUM(mij);
                if(calc==a)
                {
                    g<<mij<<'\n';
                    stop=0;
                }
                else
                if(calc<a) st=mij+1;
                else
                if(calc>a) dr=mij-1;
            }
        }
    }
    return 0;
}