#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

class Bit
{
private:
    int size;
    int* tree;
public:
    Bit(int size);
    void putValue(int value, int index);
    int getCumulative(int index);
    int getInterval(int start, int end);
    int searchIndex(int cumulative);
};

int main(int argc, const char * argv[])
{
    ifstream in("/Users/owlree/Developer/Infoarena/Arhivă educațională/Arbori indexati binar/Arbori indexati binar/aib.in");
    ofstream out("/Users/owlree/Developer/Infoarena/Arhivă educațională/Arbori indexati binar/Arbori indexati binar/aib.out");
    
    int N, M;
    in >> N >> M;
    
    Bit bit(N);
    
    for (int i = 1; i <= N; ++i)
    {
        int val;
        in >> val;
        bit.putValue(val, i);
    }
    
    for (int i = 0; i < M; ++i)
    {
        int op;
        in >> op;
        
        if (op == 0)
        {
            int index;
            int value;
            in >> index >> value;
            bit.putValue(value, index);

        }
        else if (op == 1)
        {
            int a, b;
            in >> a >> b;
            out << bit.getInterval(a, b) << "\n";
        }
        else if (op == 2)
        {
            int cumulative;
            in >> cumulative;
            out << bit.searchIndex(cumulative) << "\n";
        }
    }
    
    in.close();
    out.close();
    
    return 0;
}

Bit::Bit(int size)
{
    this->size = size;
    this->tree = new int[size + 1];
    for (int i = 0; i < size + 1; ++i)
    {
        this->tree[i] = 0;
    }
}

int Bit::getCumulative(int index)
{
    int sum = this->tree[0];
    while (index > 0)
    {
        sum += this->tree[index];
        index &= index - 1;
    }
    return sum;
}

void Bit::putValue(int value, int index)
{
    while (index <= this->size)
    {
        this->tree[index] += value;
        index = index + (index & (-index));
    }
    
}

int Bit::getInterval(int start, int end)
{
    int a = this->getCumulative(start - 1);
    int b = this->getCumulative(end);
    return b - a;
}

int Bit::searchIndex(int val)
{
    int i, step;
    
    for (step = 1; step < this->size; step <<= 1);
    for (i = 0; step; step >>= 1)
    {
        if (i + step <= this->size)
        {
            if (val >= this->tree[i + step])
            {
                i += step;
                val -= this->tree[i];
                if (!val) return i;
            }
        }
    }
    
    return -1;
}