#include <bits/stdc++.h>
#define Nmax 100005

using namespace std;

ifstream f("aib.in");
ofstream g("aib.out");

int BIT[Nmax];
int n;

void update(int pos, int val)
{
    while(pos<=n)
    {
        BIT[pos]+=val;
        pos+=(pos&(-pos));
    }
}

int query(int pos)
{
    int sum=0;
    while(pos>0)
    {
        sum+=BIT[pos];
        pos-=(pos&(-pos));
    }
    return sum;
}

int BinSearch(int expected_value)
{
    int lo=1,hi=n,mid,val;
    while(lo<=hi)
    {
        mid=(lo+hi)>>1;
        val=query(mid);
        if(val==expected_value) return mid;

        if(val<expected_value) lo=mid+1;
        else hi=mid-1;
    }
}

int main()
{
    int m,op,x,y;
    f>>n>>m;
    for(int idx=1;idx<=n;idx++)
    {
        f>>x;
        update(idx,x);
    }

    while(m--)
    {
        f>>op;
        switch (op)
        {
            case 0:
                {
                    f>>x>>y;
                    update(x,y);
                    break;
                }
            case 1:
                {
                    f>>x>>y;
                    g<<query(y)-query(x-1)<<'\n';
                    break;
                }
            case 2:
                {
                    f>>x;
                    g<<BinSearch(x)<<'\n';
                }
        }
    }

    return 0;
}