#include    <iostream>
#include    <fstream>

using namespace std;

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

const int NMax = 100005;

int N, M;
int AIB[NMax];

inline int f(int x)
{
    return (x & (-x));
}

void Update(int X, int V)
{
    for(int i = X; i <= N; i += f(i))
        AIB[i] += V;
}

int Query(int X)
{
    int Sum = 0;

    for(int i = X; i >= 0; i -= f(i))
        Sum += AIB[i];

    return Sum;
}

int BinSearch(int v)
{
    int Left, Right, Mid;
    Left = 1; Right = N;
    while(Left <= Right)
    {
        Mid = (Left + Right) / 2;

        if(Query(Mid) == v)
            return Mid;

        if(Query(Mid) < v)
            Left = Mid + 1;
        else
            Right = Mid - 1;
    }
    return -1;
}

void Read()
{
    fin >> N >> M;
    for(int i = 1; i <= N; i++)
    {
        int x;
        fin >> x;
        Update(i, x);
    }
    for(int i = 1; i <= M; i++)
    {
        int Type, X, Y;
        fin >> Type;
        if(Type == 0)
        {
            fin >> X >> Y;
            Update(X, Y);
        }
        if(Type == 1)
        {
            fin >> X >> Y;
            fout << Query(Y) - Query(X-1);
        }
        if(Type == 2)
        {
            fin >> X;
            fout << BinSearch(X);
        }
    }
}

int main()
{
    Read();
    return 0;
}