#include <iostream>
#include <fstream>
#include <string>
#include <cstring>
#include <algorithm>
#include <utility>
#include <cmath>
#include <map>
#include <deque>
#include <vector>
#include <set>
#include <queue>
#include <bitset>
#include <limits.h>
using namespace std;

#define LAST_ONE_BIT ((pos ^ (pos - 1)) & pos)

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

const int MAX_SIZE = 100000;

int n, tasks, tree[MAX_SIZE + 1], c, val, b;
 
void update(int pos, int change) {
    while (pos <= n) {
        tree[pos] += change;
        pos += LAST_ONE_BIT;
    }
}
 
int find1PosSum(int pos) {
    int sum = 0;
    while (pos) {
        sum += tree[pos];
        pos -= LAST_ONE_BIT;
    }
    return sum;
}
 
int findMinPosition(int want_sum) {
    int left = 1, right = n;
    while (left < right) {
        int mid = (left + right) / 2;
        if (find1PosSum(mid) < want_sum) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    if (find1PosSum(left) == want_sum) {
        return left;
    }
    return -1;
}
 
int main() {
    fin >> n >> tasks;
    for (int pos = 1; pos <= n; pos++) {
        fin >> val;
        update(pos, val);
    }
    for (int i = 1; i <= tasks; i++) {
        fin >> c;
        if (c == 0) {
            fin >> val >> b;
            update(val, b);
        } else if (c == 1) {
            fin >> val >> b;
            fout << find1PosSum(b) - find1PosSum(val - 1) << "\n";
        } else {
            fin >> val;
            fout << findMinPosition(val) << "\n";
        }
    }
    return 0;
}

/*
 
 
 Revin cu explicatia/ideea de baza pentru arborele indexat binar si cum il vom crea:
 
 - plecam de la root-ul care va fi pozitia "0" si in care nu vom stoca nimic
 - pentru o pozitie "x", sa spunem ca aceasta il are ca si parinte pe pozitia "y". Pozitia "y" este numarul format prin a inlocui cel mai din dreapta bit "1" din reprezentarea binara a pozitiei "x" cu "0".
 OBS: orice numar poate fi reprezentat ca o suma de puteri ale lui 2. ex: 11 = 2^3 + 2^1 + 2^0
 = 8 + 2 + 1 = 11 (A)
 
 Astfel, mergand pe cerinta problemei, ca sa ne dam seama ce suma vrem sa stocam pe pozitia "x", va trebui sa scriem pozitia "x" ca pe o suma de puteri ale lui 2. Exemple:
 1)
 11 = 2^3 + 2^1 + 2^0
 Astfel, insumand primele 2 elemente si lasand liber ultimul termen, vom avea 2 numere: 10 si 1.
 Deci, incepand de la pozitia "10" vom stoca pe pozitia "11" din arbore urmatoarele "1" elemente, astfel obtinand suma din intervalul (10, 10) (daca indexam sirul initial de la pozitia 0)
 2)
 8 = 0 + 2^3. Astfel, plecand de la pozitia "0", vom stoca pe pozitia "8" din arbore urmatoarele 8 elemente, obtinand suma din intervalul (0, 7)
 
3)
 6 = 2^2 + 2^1. Astfel, plecand de la pozitia "4", vom stoca pe pozitia "6" din arbore urmatoarele "2" elemente, obtinand suma din intervalul (4, 5)
 
 etc.
 
 Cum facem lucrul asta in cod, astfel incat sa ne asiguram ca formam bine arborele de fiecare data?
 
 - functia "update", in care actualizam toate pozitiile "complementare" adaugand valoarea de pe pozitia curenta din sir tuturor pozitiilor "complementare". Pornind de la pozitia din sir, si adaugandu-i acestei pozitii valoarea "((pos ^ (pos - 1)) & pos)" de fiecare data pentru a gasi urmatoarea pozitie "complementara", adunam valorii din arbore "tree[pos]" valoarea din "sir[pos]". Facem acest lucru doar cat timp pozitia "pos" este mai mica sau egala decat lungimea sirului, deoarece avem nevoie de fix lungimea sirului pozitii pentru a forma acest arbore.
 Pe scurt, vrem sa adaugam valoarea "sir[pos]" tuturor pozitiilor din arbore ce reprezinta un interval care include aceasta pozitie, similar ca la arborii binari, numai ca aici reprezentarea e diferita si mai eficienta.
 
 - in functia "findMinPosition" (cu ajutorul careia returnam suma elementelor de la pozitia "1" pana la "pos"), vom face lucrurile fix pe dos, avand deja arborele format. Vrem sa plecam de la pozitia "pos" si sa mergem invers fata de cum formam/actualizam arborele. Scadem din "pos" valoarea lui "((pos ^ (pos - 1)) & pos)" si actualizam valoarea unei variabile in care stocam suma, adaugand valoarea de pe pozitia "pos" din arbore, "tree[pos]".
 
 - in functia "findMinPosition" doar aplicam o cautare binara clasica, ajutandu-ne de functia "findMinPosition". Nimic special.
 
 
 
 De exemplu, pentru un sir de 20 de elemente, acestea sunt pozitiile "complementare" parcurse plecand de la fiecare pozitie in parte:
 1 2 4 8 16
 2 4 8 16
 3 4 8 16
 4 8 16
 5 6 8 16
 6 8 16
 7 8 16
 8 16
 9 10 12 16
 10 12 16
 11 12 16
 12 16
 13 14 16
 14 16
 15 16
 16
 17 18 20
 18 20
 19 20
 20
 
 Observam ca ne folosim de fix "lungimea sirului" pozitii.
 
Ok, am inteles care e ideea si cum ne putem folosi de arborii indexati binar.
Mi se par destul de incurcate operatiile pe biti, mai ales: "((pos ^ (pos - 1)) & pos)".
 Trebuie sa stapanesti bine si reprezentarea in baza 2 a numerelor si ce fac operatorii specifici.
 
 Daca gresesc ceva/am omis ceva, te rog sa imi spui. :)
 Mersi pentru sfaturi!
 
 
 */