#include <bits/stdc++.h>
#define NMAX 100005

using namespace std;

/*******************************/
// INPUT / OUTPUT

ifstream f("aib.in");
ofstream g("aib.out");
/*******************************/
/// GLOBAL DECLARATIONS

int N, M;
int aib[NMAX];
/*******************************/
/// FUNCTIONS

void ReadInput();
void Solution();
/*******************************/
///-------------------------------------
void update(int val, int pos)
{
    while (pos <= N)
    {
        aib[pos] += val;
        pos += pos & (-pos);
    }
}
///-------------------------------------
inline void ReadInput()
{
    f >> N >> M;

    int num;
    for (int i = 1 ; i <= N ; ++ i)
    {
        f >> num;
        update(num, i);
    }
}
///-------------------------------------
int query1(int pos)
{
    int sum = 0;
    while (pos)
    {
        sum += aib[pos];
        pos -= pos & (-pos);
    }

    return sum;
}
///-------------------------------------
int query2(int target)
{
    int step = (1 << int(log2(N)));

    int sum = 0, pos = 0;

    while (step)
    {
        if (pos + step <= N && sum + aib[sum + step] < target)
        {
            pos += step;
            sum += aib[step];
        }
        step >>= 1;
    }

    return query1(pos + 1) == target ? pos + 1 : -1;
}
///-------------------------------------
inline void Solution()
{
    int tip, a, b;
    while (M --)
    {
        f >> tip;

        if (tip == 0)
        {
            f >> a >> b;
            update(b, a);
        }
        else
        {
            if (tip == 1)
            {
                f >> a >> b;
                g << query1(b) - query1(a - 1) << "\n";
            }
            else
            {
                f >> a;
                g << query2(a) << "\n";
            }
        }
    }
}
///-------------------------------------
int main()
{
    ReadInput();
    Solution();
    return 0;
}