#include <fstream>
#include <iostream>
using namespace std;

#define nmax 100001
ifstream fi("aib.in");
ofstream fo("aib.out");

int n,m,i,tip,poz,v,st,dr,x;
unsigned long long S[nmax];

void update(int poz, int v) {
    
    int w;
    
    while (poz <= n) {
        
        S[poz] += v;
        
        w = (poz^(poz-1))&poz;
        
        poz += w;
        
    }
    
}

int f(int p) {
    
    int total = 0, w;
    
    while (p > 0) {
        
        total += S[p];
        
        w = (p^(p-1))&p;
        
        p -= w;
        
    }
    
    return total;
    
}

void doi(int x) {
    
    int hi = n, lo = 1, mid;
    
    while (lo <= hi) {
        
        mid = (hi + lo) / 2;
        
        int l = f(mid);
        
        if (l == x) {
            
            fo << mid << "\n";
            return;
            
        } else if (l < x) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
        
    }
    
    fo << "-1\n";
    
}

int main() {
    
    fi >> n >> m;
    
    for (i=1; i<=n; i++) {
        
        fi >> x;
        
        update(i, x);
        
    }
    
    for (i=1; i<=m; i++) {
        
        fi >> tip;
    
        if (tip == 0) {
            
            fi >> poz >> v;
            
            update(poz, v);
            
        } else if (tip == 1) {
            
            fi >> st >> dr;
            
            fo << f(dr) - f(st-1) << "\n";
            
        } else {
            
            fi >> x;
            
            doi(x);
            
        }
        
    }
    
    
    return 0;
}