#include <bits/stdc++.h>
#define LSB(x) (x & -x)
using namespace std;

class InputReader
{
public:
    InputReader() {}
    InputReader(const char *file_name)
    {
        input_file = fopen(file_name, "r");
        cursor = 0;
        fread(buffer, SIZE, 1, input_file);
    }
    inline InputReader &operator >>(int &n)
    {
        while(buffer[cursor] < '0' || buffer[cursor] > '9')
        {
            advance();
        }
        n = 0;
        while('0' <= buffer[cursor] && buffer[cursor] <= '9')
        {
            n = n * 10 + buffer[cursor] - '0';
            advance();
        }
        return *this;
    }
private:
    FILE *input_file;
    static const int SIZE = 1 << 17;
    int cursor;
    char buffer[SIZE];
    inline void advance()
    {
        ++ cursor;
        if(cursor == SIZE)
        {
            cursor = 0;
            fread(buffer, SIZE, 1, input_file);
        }
    }
};

int n,m,t;

class AIB
{
    public:
        inline void update(int idx, const int &x)
        {
            for (; idx<=n; idx+=LSB(idx))   AIB[idx] += x;
        }

        inline int Sum(int idx)
        {
            int s = 0;
            for (; idx>=1; idx-=LSB(idx))   s+=AIB[idx];
            return s;
        }

        inline int rangeQuery(int a,int b)
        {
            return Sum(b)-Sum(a-1);
        }

        inline int dubiosQuery(int idx)
        {
            int st=1,dr=n;
            while (st<=dr)
            {
                int mij=(st+dr)/2;
                int nr=Sum(mij);
                if (nr==idx) return mij;
                if (nr<idx) st=mij+1;
                else dr=mij-1;
            }
            return -1;
        }

    private:
        int AIB[100001]= {0};

};


int main()
{
    InputReader f("aib.in");
    ofstream g("aib.out");
    AIB myAIB;

    int a,b;
    f>>n>>m;
    for(int i=1; i<=n; i++)
    {
        f>>a;
        myAIB.update(i, a);
    }


    for(int i=1; i<=m; i++)
    {
        f>>t;
        if(t==0)
        {
            f>>a>>b;
            myAIB.update(a, b);
        }
        else if(t==1)
        {
            f>>a>>b;
            g<<myAIB.rangeQuery(a,b)<<'\n';
        }
        else if(t==2)
        {
            f>>a;
            g<<myAIB.dubiosQuery(a)<<'\n';
        }
    }

}