#include <bits/stdc++.h>

using namespace std;

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

class BIT
{
    private:
        int *a,N;
        void desc(int &x)
        {
            x-=(x&(-x));
        }

        void asc(int &x)
        {
            x+=(x&(-x));
        }

    public:
        BIT(int n)
        {
            a=new int[n+5]();
            N=n;
        }

        void update(int poz, int val)
        {
            while(poz<=N)
            {
                a[poz]+=val;
                asc(poz);
            }
        }

        int query(int poz)
        {
            int sum=0;
            while(poz>0)
            {
                sum+=a[poz];
                desc(poz);
            }
            return sum;
        }

        int S_bin(int val)
        {
            int lo=1,hi=N,mid,s;
            while(lo<=hi)
            {
                mid=(lo+hi)>>1;
                s=query(mid);

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

int main()
{
    int n,i,x,y,op,m;
    f>>n>>m;

    BIT v(n);

    for(i=1;i<=n;i++)
    {
        f>>x;
        v.update(i,x);
    }

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

    return 0;
}