#include <bits/stdc++.h>
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;
vector <int> V;

class AIB
{

public:
    AIB(std::vector<int> list)
    {
        m_array = std::vector<int>(list.size() + 1, 0);
        for (int idx = 0; idx < list.size(); idx++)
        {
            m_array[idx + 1] = list[idx];
        }

        for (int idx = 1; idx < m_array.size(); idx++)
        {
            int idx2 = idx + (idx & -idx);
            if (idx2 < m_array.size())
            {
                m_array[idx2] += m_array[idx];
            }
        }
    }

    int prefix_query(int idx)
    {
        int result = 0;
        for (++idx; idx > 0; idx -= idx & -idx)
        {
            result += m_array[idx];
        }
        return result;
    }

    int range_query(int from_idx, int to_idx)
    {
        return prefix_query(to_idx) - prefix_query(from_idx - 1);
    }

    void update(int idx, int add)
    {
        for (++idx; idx < m_array.size(); idx += idx & -idx)
        {
            m_array[idx] += add;
        }
    }

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

private:
    std::vector<int> m_array;
};

int main()
{
    InputReader f("aib.in");
    ofstream g("aib.out");
    V.push_back(0);
    int a,b;
    f>>n>>m;
    for(int i=1; i<=n; i++)
    {
        f>>a;
        V.push_back(a);
    }

    AIB myAIB(V);

    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.range_query(a,b)<<'\n';
        }
        else if(t==2)
        {
            f>>a;
            g<<myAIB.dubios_query(a)<<'\n';
        }
    }

}