#include <fstream>
#define NMAX 100005
using namespace std;
ifstream  fin("aib.in");
ofstream fout("aib.out");
int N,M,v[NMAX],aib[NMAX];

void citire()
{
    fin>>N>>M;

    for(int i=1; i<=N; i++)
    {
        fin>>v[i];
    }
}

void update(int x, int val)
{
    for(int i=x; i<=N; i+=(i&-i))
    {
        aib[i]+=val;
    }
}

int query(int x)
{
    int ans=0;
    for(int i=x; i>=1; i-=(i&-i))
    {
        ans+=aib[i];
    }
    return ans;
}

int main()
{
    citire();

    for(int i=1; i<=N; i++)
    {
        update(i,v[i]);
    }

    int op,a,b;
    for(int q=1; q<=M; q++)
    {
        fin>>op;

        if(op==0)
        {
            fin>>a>>b;
            v[a]+=b;
            update(a,b);
        }

        if(op==1)
        {
            fin>>a>>b;
            fout<< query(b)-query(a-1) << "\n";
        }

        if(op==2)
        {
            fin>>a;

            int p1,p2,pmijl,ans;
            p1=1;
            p2=N;
            ans=-1;

            while(p1<=p2)
            {
                pmijl=(p1+p2)/2;

                int sum=query(pmijl);

                if(sum==a)
                {
                    ans=pmijl;
                    break;
                }
                else
                {
                    if(sum>a)
                    {
                        p2=pmijl-1;
                    }
                    else
                    {
                        p1=pmijl+1;
                    }
                }
            }

            fout<< ans << "\n";
        }
    }

    return 0;
}