#include <fstream>
#define InFile  "aib.in"
#define OutFile "aib.out"
#define MAX 100001

using namespace std;

void add (int position, int value);
int sum (int position);
int binsrc (int value);

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

int BIT[MAX];
int i;

int solution, k;

int main ()
{
    ifstream fin (InFile);
    ofstream fout (OutFile);
    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;
            solution = sum(b) - sum(a-1);
            fout << solution;
            fout << '\n';
        }
        else
        {
            fin >> a;
            k = binsrc(a);
            fout << k;
            fout << '\n';
        }
    }
    fin.close();
    fout.close();
    return 0;
}

void add (int position, int value)
{
    while (position <= N)
    {
        BIT[position] += value;
        position += (position^(position-1))&position;
    }
}

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

int binsrc (int value)
{
    int k, i;
    k = 1;
    i = 0;
    while (k < N)
        k *= 2;
    while (k > 0)
    {
        if (i+k <= N)
        {
            if (sum(i+k) == value)
                return i+k;
            else if (sum(i+k) < value)
                i += value;
        }
        k /= 2;
    }
    return -1;
}