#include <fstream>
#include <vector>

using namespace std;

struct Node
{
    int sum;
    Node* left, * right;
    Node(int sum) : sum(sum), left(nullptr), right(nullptr) {}
};

void addOrChangeNode(int v, int pos, int left, int right, Node*& root)
{
    if (pos > right || pos < left)
    {
        return;
    }

    if (left == right && pos == left)
    {
        root->sum += v;
        return;
    }

    int mid = left + (right - left) / 2;

    if (pos <= mid)
    {
        if (root->left == nullptr)
            root->left = new Node(0);
        addOrChangeNode(v, pos, left, mid, root->left);
    }
    else
    {
        if (root->right == nullptr)
            root->right = new Node(0);
        addOrChangeNode(v, pos, mid + 1, right, root->right);
    }

    root->sum += v;
}

int getSum(int l, int r, int left, int right, Node*& root)
{
    if (r < left || l > right)
        return 0;

    if (l <= left && right <= r)
        return root->sum;

    int leftSum = 0, rightSum = 0;
    int mid = left + (right - left) / 2;
    if (mid >= l)
    {
        leftSum = getSum(l, r, left, mid, root->left);
    }
    if (mid < r)
    {
        rightSum = getSum(l, r, mid + 1, right, root->right);
    }
    return leftSum + rightSum;

}

int findSumPosition(int sum, int left, int right, Node*& root)
{
    if (sum == root->sum) return right;
    if (sum > root->sum) return -1;
    if (left == right) return -1;

    int mid = left + (right - left) / 2;
    if (sum > root->left->sum)
        return findSumPosition(sum - root->left->sum, mid + 1, right, root->right);
    else
        return findSumPosition(sum, left, mid, root->left);
}

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

    int n, m;
    fin >> n >> m;

    int capacity = 1;
    while (capacity < n)
        capacity *= 2;


    Node* root = new Node(0);
    for (int i = 0; i < n; ++i)
    {
        int x;
        fin >> x;
        addOrChangeNode(x, i + 1, 1, n, root);
    }

    for (int i = 0; i < m; ++i)
    {
        int task;
        fin >> task;
        if (task == 0)
        {
            int pos, v;
            fin >> pos >> v;
            addOrChangeNode(v, pos, 1, n, root);
        }
        else if (task == 1)
        {
            int left, right;
            fin >> left >> right;
            fout << getSum(left, right, 1, n, root) << endl;
        }
        else
        {
            int sum;
            fin >> sum;
            fout << findSumPosition(sum, 1, n, root) << endl;
        }
    }

}