//
//  main.cpp
//  Arbori indexati binar
//
//  Created by Robert Badea on 3/23/14.
//  Copyright (c) 2014 Sliderr. All rights reserved.
//

#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("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;
        // cout << i << " - " << op << ":\n";
        if (op == 0)
        {
            int index;
            int value;
            in >> index >> value;
            // cout << index << " " << value << "\n";
            bit.putValue(value, index);

        }
        else if (op == 1)
        {
            int a, b;
            in >> a >> b;
            // cout << a << " to " << b << "\n";
            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;
        // cout << "add " << value << " at " << index << "\n";
        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 cumulative)
{
    int index = 0;
    int bitMask = 1;
    for (bitMask = 1; bitMask < this->size; bitMask <<= 1);
    
    /*
    cout << "bitMask: " << bitMask << "\n";
    cout << "size: " << this->size << "\n\n";
     */
    
    if (cumulative > this->tree[0])
    {
        while (bitMask != 0)
        {
            /*
            cout << "bitMask: " << bitMask << "\n";
            cout << "cumulative: " << cumulative << "\n";
            cout << "here: " << this->tree[index + bitMask] << "\n\n";
             */
            
            int textIndex = index + bitMask;
            if (cumulative >= this->tree[index + bitMask])
            {
                index = textIndex;
                cumulative -= this->tree[index];
                if (cumulative == 0) return index;
            }
            bitMask /= 2;
        }
    }
    
    return -1;
}