#include <stdio.h>

#define maxl 100010

int n,m,k,i,j,tip,p,q,sol;
int a[maxl],aib[maxl];

int lsb(int x) {
    return x ^ (x & (x - 1));
}

void update(int x, int val) {
     k = x;
     while (k <= n) {
           aib[k] += val;
           k += lsb(k);
     }
}

int suma(int k) {
    int sum = 0, x = k;
    
    while (x) {
          sum += aib[x];
          x -= lsb(x);
    }
    
    return sum;
}

int main() {

    freopen("aib.in","r",stdin);
    freopen("aib.out","w",stdout);
    
    scanf("%d %d",&n,&m);
    for (i = 1; i <= n; i++) {
        scanf("%d",&a[i]);
        update(i,a[i]);
    }
    
    for (i = 1; i <= m; i++) {
        scanf("%d %d",&tip,&p);
        if (tip != 2) scanf("%d",&q);
        
        if (tip == 0) {
           update(p,q);
        }
        else if (tip == 1) {
                printf("%d\n",suma(q) - suma(p - 1));
             }
             else {
                  int x = 0, y = n + 1 , r;
                  while (x + 1 < y) {
                        r = (x + y) / 2;
                        if (suma(r) > p)  y = r;
                        else if (suma(r) < p) x = r;
                             else {
                                 sol = r;
                                 y = r;
                             }
                  }  
                  printf("%d\n",sol);
             }
    }
    
    return 0;
}