#include <fstream>
using namespace std;
ifstream f("aib.in"); ofstream g("aib.out");
int n, m, AIB[100001];
int Zero(int x)
{
    return x&-x;
}
void Update(int poz, int val)
{
    for(; poz<=n; poz+=Zero(poz)) AIB[poz]+=val;
}
int Calc(int poz)
{
    int s=0;
    for(;poz;poz-=Zero(poz)) s+=AIB[poz];
    return s;
}
int main()
{
    f>>n>>m;
    for(int v, i=1; i<=n; i++)
    {
        f>>v;
        Update(i, v);
    }
    int t, a, b;
    while(m--)
    {
        f>>t;
        switch(t)
        {
            case 0:
            {
                f>>a>>b;
                Update(a, b);
                break;
            }
            case 1:
            {
                f>>a>>b;
                g<<Calc(b)-Calc(a-1)<<'\n';
                break;
            }
            default:
            {
                f>>a;
                int d=n, s=1, m;
                while(s<=d)
                {
                    m=(d+s)/2;
                    if(AIB[m]==a)
                    {
                        while(AIB[m]==a) m--;
                        g<<m+1<<'\n'; s=d+1;

                    }
                    else if(AIB[m]<a) s=m+1;
                    else d=m-1;
                }
            }
        }
    }
    return 0;
}