#include <fstream>

using namespace std;

ifstream fin ("aib.in");
ofstream fout ("aib.out");

inline void ADD (unsigned int pos, unsigned int val);
inline unsigned int SUM (unsigned int pos);
inline int BIN_SRC (unsigned int val);

unsigned int N, M;
unsigned int A;
unsigned int type;
unsigned int a, b;

unsigned int BIT[100001];     /// BIT = Binary Indexed Tree
unsigned int i;

int sol;

int main ()
{
    fin >> N >> M;
    for (i=1; i<=N; i++)
    {
        fin >> A;
        ADD(i,A);
    }
    for (i=1; i<=M; i++)
    {
        fin >> type;
        if (type == 0)
        {
            fin >> a >> b;
            ADD(a,b);
        }
        else
            if (type == 1)
            {
                fin >> a >> b;
                sol = SUM(b) - SUM(a-1);
                fout << sol << '\n';
            }
            else
            {
                fin >> a;
                sol = BIN_SRC(a);
                fout << sol << '\n';
            }
    }
    return 0;
}

inline void ADD (unsigned int pos, unsigned int val)
{
    while (pos <= N)
    {
        BIT[pos] += val;
        pos += (pos^(pos-1))&pos;
    }
}

inline unsigned int SUM (unsigned int pos)
{
    unsigned int sum;
    sum = 0;
    while (pos > 0)
    {
        sum += BIT[pos];
        pos -= (pos^(pos-1))&pos;
    }
    return sum;
}

inline int BIN_SRC (unsigned int val)
{
    unsigned int i, k;
    i = 0;
    k = 1;
    while (k < N)
        k *= 2;
    while (k > 0)
    {
        if (i+k <= N)
            if (SUM(i+k) == val)
                return i+k;
            else
                if (SUM(i+k) < val)
                    i += k;
        k /= 2;
    }
    return -1;
}