#include <fstream>
#define DIM 100010
using namespace std;

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

int N, M, i, j, cod, Y;
int aib[DIM], X;

void Update(int A, int B){
    for(A = A; A <= N; A += (A&(-A)))
        aib[A] += B;
    return;
}

void SetUp(){
    fin >> N >> M;
    for(i = 1; i <= N; i ++){
        fin >> X;
        Update(i, X);
    }
    return;
}

int Query(int A){
    int val = 0;
    for(A = A; A >= 1; A -= (A&(-A)))
        val += aib[A];
    return val;
}

int CautBin(int val){
    int st = 1, dr = N;
    while(st <= dr){
        int mid = st + (dr - st) / 2;
        if(Query(mid) == val)
            return mid;
        if(Query(mid) < val)
            st = mid + 1;
        else
            dr = mid - 1;
    }
    return -1;
}

void CodeExpert(){
    for(i = 1; i <= M; i ++){
        fin >> cod >> X;
        if(cod != 2)
            fin >> Y;
        switch(cod)
        {
            case 0:{Update(X, Y);break;}
            case 1:{fout<<Query(Y) - Query(X-1) << "\n";break;}
            case 2:{fout<<CautBin(X) << "\n";break;}
        }
    }
    return;
}

int main(){
    SetUp();
    CodeExpert();
    return 0;
}