#include <bits/stdc++.h>

using namespace std;

ifstream f("aib.in");
ofstream g("aib.out");

int n, m, x, t, a, b;
vector<int> aib;

void update(int pos, int val)
{
    for (int i = pos; i <= n; i += i & -i)
        aib[i] += val;
}

int query(int pos)
{
    int sum = 0;
    for (int i = pos; i > 0; i -= i & -i)
        sum += aib[i];

    return sum;
}

int findKSum(int left, int right, int sum)
{
    if (left == right)
        return query(left) == sum ? left : -1;

    int mid = left + (right - left) / 2;
    if (sum <= query(mid))
        return findKSum(left, mid, sum);
    else
        return findKSum(mid + 1, right, sum);
}

int main()
{
    f >> n >> m;

    aib.resize(2 * n + 4, 0);

    for (int i = 1; i <= n; ++i)
        f >> x,
        update(i, x);

    while (m--)
    {
        f >> t;
        if (t == 0)
            f >> a >> b,
            update(a, b);
        else if (t == 1)
            f >> a >> b,
            g << query(b) - query(a - 1) << '\n';
        else
            f >> a,
            g << findKSum(1, n, a) << '\n';
    }

    return 0;
}