#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int a[N], pos[N], L[N], R[N], SIZE[N], g[N], tag[N], val[N];

int f[2][N], ans[N], fs[2], anss; // 归并用 

void merge () {
  int i = 0, j = 0; anss = 0;
  
  while (i < fs[0] and j < fs[1]) {
    
    if (a[f[0][i + 1]] < a[f[1][j + 1]])
      ans[++ anss] = f[0][++ i];
    else ans[++ anss] = f[1][++ j];  
    
  }
  
  while (i < fs[0]) ans[++ anss] = f[0][++ i];
  while (j < fs[1]) ans[++ anss] = f[1][++ j]; 

}

void merge2 () {
  int i = 0, j = 0; anss = 0;
  
  while (i < fs[0] and j < fs[1]) {
    
    if (f[0][i + 1] < f[1][j + 1])
      ans[++ anss] = f[0][++ i];
    else ans[++ anss] = f[1][++ j];  
    
  }

  while (i < fs[0]) ans[++ anss] = f[0][++ i];
  while (j < fs[1]) ans[++ anss] = f[1][++ j]; 

}

void upd (int id, int l, int r) {
  fs[0] = fs[1] = 0;
  for (int i = L[id]; i <= R[id]; i ++) {
    
    if (g[i] >= l and g[i] <= r)
      f[0][++ fs[0]] = g[i];
    else f[1][++ fs[1]] = g[i];
    
  }
  
  merge ();
  
  for (int i = L[id]; i <= R[id]; i ++) 
    g[i] = ans[i - L[id] + 1], val[i] = a[g[i]];
}

void update (int l, int r, int v) {
  if (pos[l] == pos[r]) {
    
    for (int i = l; i <= r; i ++) 
      a[i] += v;
      
    upd (pos[l], l, r);    
    
    return ;
  }
  
  for (int i = l; i <= R[pos[l]]; i ++)
    a[i] += v;
  upd (pos[l], l, R[pos[l]]);
  
  for (int i = L[pos[r]]; i <= r; i ++)
    a[i] += v;
  upd (pos[r], L[pos[r]], r);
  
  for (int i = pos[l] + 1; i <= pos[r] - 1; i ++)
    tag[i] += v;
  
}

void divide (int id, int G, int l, int r) { // 从 id 块的 g 中抽取 l-r 的数，放到 f[G]
  
  fs[G] = 0;
  
  for (int i = L[id]; i <= R[id]; i ++)
    if (g[i] >= l and g[i] <= r) 
      f[G][++ fs[G]] = a[g[i]] - tag[id];
      
}

int check (int *Q, int l, int r, int x) { // 查找 Q 数组的区间 [l, r] 中 x 的排名 
  //cout << "fdhsklfa " << l <<  " " << r << " " << x << "\n"; 
  return upper_bound (Q + l, Q + r + 1, x) - (Q + l); 
}

int check2 (int idl, int idr, int x) {
  
  if (idl > idr) return 0;
  
  int ans = 0;
  
  for (int i = idl; i <= idr; i ++)
    ans += check (val, L[i], R[i], x - tag[i]);
  
  //cout << idl << "->" << idr << " " << x << " " << ans << "\n";
  
  return ans;
}

int ask (int l, int r, int k) {
  
  if (pos[l] == pos[r]) {
    divide (pos[l], 0, l, r);
    
   /* for (int i = 1; i <= fs[0]; i ++)
      cout << f[0][i] << " ";
    cout << "Yes\n";
   */
    
    int lt = -2e9, rt = 2e9;
    
    while (lt + 1 < rt) {
      
      int mid = lt + (rt - lt) / 2;
      if (check (f[0], 1, fs[0], mid) >= k) rt = mid;
      else lt = mid; 
    
    } 
    
    return rt;
    
  } 
  
  divide (pos[l], 0, l, R[pos[l]]);
  divide (pos[r], 1, L[pos[r]], r);
  
  merge2 ();
  
/*  for (int i = 1; i <= anss; i ++)
    cout << ans[i] << " ";
  cout << "ha\n";  
*/
  
//  cout << pos[l] + 1 << " " << pos[r] - 1 << "gg\n";
  
  int lt = -2e9, rt = 2e9;
  
  while (lt + 1 < rt) {
    
    int mid = lt + (rt - lt) / 2;
    
    if (check2 (pos[l] + 1, pos[r] - 1, mid) + check (ans, 1, anss, mid) >= k) rt = mid;
    else lt = mid;
    
  }
  
  return rt;
  
}

int main () {
  int n, m, siz, num; cin >> n >> m;
  
  siz = sqrt (n) * min ((int)log2 (n), 1);  num = n / siz + (n % siz != 0);
  
 // cout << "size is" << siz << "\n";
  
  for (int i = 1; i <= n; i ++) 
    cin >> a[i];
  
  for (int i = 1; i <= n; i ++)
    pos[i] = (i - 1) / siz + 1;
    
  for (int i = 1; i <= num; i ++) {
    
    L[i] = (i - 1) * siz + 1;
    R[i] = i * siz;
    if (i == num) R[i] = n;
    
    SIZE[i] = R[i] - L[i] + 1;
    
    for (int j = L[i]; j <= R[i]; j ++)
      g[j] = j;
      
    sort (g + L[i], g + R[i] + 1, [] (int x, int y) {
      return a[x] < a[y];
    });    
    
    for (int j = L[i]; j <= R[i]; j ++)
      val[j] = a[g[j]];
    
  }
  
  
  while (m --) {
    
    int opt, l, r, k;
    
    cin >> opt >> l >> r >> k;
    
    if (opt == 1)
      cout << ask (l, r, k) << "\n";
    else upd (l, r, k);
    
  }
  
}

/*

10 10
7157 27211 7778 11271 12240 24315 8149 14437 19151 30450 
1 8 5
1 8 5
1 8 8
1 8 7
1 8 1
1 8 4
1 8 4
1 8 8
1 8 8
1 8 3


*/