#include<cstdio>
    #include<fstream>
    using namespace std;
    #define MAX 100001
    int N , M , x , y , z , AIB[MAX];

    void update(int x, int y);
    int query(int a);
    int search(int a);

    int main()
    {
        ifstream f("aib.in");
        ofstream g("aib.out");
        f>>N>>M;
        for(int i = 1 ; i <= N ; ++i )
        {
            f>>x;
            update(i,x);
        }
        for(int i = 1 ; i<=M;++i)
        {
            f>>z;
            if(z == 0)
            {
                f>>x>>y;
                update(x,y);
            }
            else
                if(z == 1)
                {
                    f>>x>>y;
                    g<<query(y)-query(x-1)<<"\n";
                }
                else
                {
                    f>>x;
                    g<<search(x)<<"\n";
                }
        }
    }

    void update(int x,int y)
    {
        int k = 0;
        while(x <= N)
        {
            AIB[x] += y;
            while(!(x&(1<<k)))k++;
            x+=(1<<k);
            k++;
        }
    }

    int query(int x)
    {
        int s = 0 , k = 0;
        while(x > 0)
        {
            s+=AIB[x];
            while(!(x&(1<<k)))k++;
            x-=(1<<k);
            k++;
        }
        return s;
    }

    int search(int x)
    {
        int st = 1 , dr = N , m , t;
        while(st <= dr)
        {
            m = (st+dr)/2;
            t = query(m);
            if(t == x)return m;
            else
                if(t > x)dr = m-1;
                else
                    st = m+1;
        }
        return -1;
    }