#include <fstream>
#include <iostream>
#include <cmath>

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

int Tree[270005], imax, mp2, r;

int build_Tree(int i, int n)
{
    if(2 * i > imax) fin >> Tree[i];
    else Tree[i] = build_Tree(2 * i, n+1) + build_Tree(2 * i + 1, n+1);

    return Tree[i];
}

int max2n(int n)
{
    int x = 1;
    while(2 * x <= n) x *= 2;
    return x;
}

void update_Tree(int a, int b)
{
    int i;
    if(a <= 2 * r) i = 2 * mp2 + a - 1;
        else i = mp2 + a - r - 1;

    for(;i > 0; i /= 2) Tree[i] += b;
}

int sum(int a, int b)
{
    int ss, sd;
    if(a <= 2 * r) {a = 2 * mp2 + a - 1;
        if(a % 2 == 0) ss = Tree[a/2]; else ss = Tree[a]; a /= 2;
    }else a = mp2 + a - r - 1, ss = Tree[a];
    if(b <= 2 * r){ b = 2 * mp2 + b - 1;
        if(b % 2 == 1) sd = Tree[b/2]; else sd = Tree[b]; b /= 2;
    }else b = mp2 + b - r - 1, sd = Tree[b];

    if(a == b) return min(ss, sd);

    for(; a/2 != b/2; a /= 2, b /= 2){
        if(a % 2 == 0) ss += Tree[a + 1];
        if(b % 2 == 1) sd += Tree[b - 1];
    }

    return ss + sd;
}

int lrmost(int x, bool right)
{
    while(2 * x + right <= imax)
        x = x * 2 + right;
        return x;
}

int smallestk(int a)
{
    int i = lrmost(1, 0);

    if(a == Tree[1]) a = 0, i = 1;

    while(a > 0 && i > 0 && i <= imax){
        if(Tree[i / 2] >= a){
            a -= Tree[i];
            if(a) i = lrmost(i + 1, 0);
        }
        else i = i / 2;
    }
    i = lrmost(i, 1);
    if(!a) return i - max2n(i) + 1;
        return -1;
}

int main()
{
    int m, n, a, b, t, i;

    fin >> n >> m;
    mp2 = max2n(n); r = n - mp2;
    imax = 2 * mp2 - 1 + 2 * r;
    build_Tree(1, 1);

    for(i = 1; i <= m; i++){
        fin >> t;
        if(t == 0) fin >> a >> b, update_Tree(a, b);
        else if(t == 1) fin >> a >> b, fout << sum(a, b) << "\n";
             else if(t == 2) fin >> a, fout << smallestk(a) << "\n";
    }

    return 0;
}