#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;
#define int long long
#define inline inline __attribute__((always_inline))
#define LOCAL
namespace ly {
	namespace IO {
#ifndef LOCAL
		constexpr auto maxn = 1 << 20;
		char in[maxn], out[maxn], *p1 = in, *p2 = in, *p3 = out;
#define getchar() (p1 == p2 && (p2 = (p1 = in) + fread(in, 1, maxn, stdin), p1 == p2) ? EOF : *p1++)
#define flush() (fwrite(out, 1, p3-out, stdout))
#define putchar(x) (p3 == out + maxn && (flush(), p3 = out), *p3++ = (x))
		class Flush {
			public :
				~Flush() {
					flush();
				}
		} _;
#endif
		namespace usr {
			template <typename type>
			inline type read(type &x) {
				x = 0;
				bool flag(0);
				char ch = getchar();
				while(!isdigit(ch)) flag ^= ch == '-', ch = getchar();
				while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
				return flag ? x = -x : x;
			}
			template<typename type>
			inline void write(type x) {
				x < 0 ? x = -x, putchar('-') : 0;
				static short Stack[50], top(0);
				do Stack[++top] = x % 10, x /= 10;
				while(x);
				while(top) putchar(Stack[top--] | 48);
			}
			inline char read(char &x) {
				do x = getchar();
				while(isspace(x));
				return x;
			}
			inline char write(const char &x) {
				return putchar(x);
			}
			inline void read(char *x) {
				static char ch;
				read(ch);
				do *(x++) = ch;
				while(!isspace(ch = getchar()) && ~ch);
			}
			template <typename type>
			inline void write(type *x) {
				while(*x) putchar(*(x++));
			}
			inline void read(string &x) {
				static char ch;
				read(ch), x.clear();
				do x += ch;
				while(!isspace(ch = getchar()) && ~ch);
			}
			inline void write(const string &x) {
				for(int i = 0, len = x.length(); i < len; ++i) putchar(x[i]);
			}
			template <typename type, typename...T>
			inline void read(type &x, T&...y) {
				read(x), read(y...);
			}
			template <typename type, typename...T>
			inline void write(const type &x, const T&...y) {
				write(x), putchar(' '), write(y...), sizeof...(y) ^ 1 ? 0 : putchar('\n');
			}
			template <typename type>
			inline void put(const type &x, bool flag = 1) {
				write(x), flag ? putchar('\n') : putchar(' ');
			}
		}
#ifndef LOCAL
#undef getchar
#undef flush
#undef putchar
#endif
	}
	using namespace IO :: usr;
}
using namespace ly :: IO :: usr;
const int N = 1e5 + 10, INF = 1 << 25;
int n, S;
template <typename T>
struct vector_tree{
    vector <vector <T> > v;
    vector_tree () {
        v.emplace_back();
	    v.back().emplace_back(INF);
    }
    inline T find(T x, T l, T r) {
        for(size_t i = l; i <= r; i++) if (v[i].back() >= x) return i;
        return 0;
    }
    inline void split(T p) {
        v.emplace(v.begin() + p + 1, v[p].begin() + S, v[p].end());
        v[p].erase(v[p].begin() + S, v[p].end());
    }
    inline void insert(T x) {
        T p = find(x, 0, v.size());
        v[p].emplace(lower_bound(v[p].begin(), v[p].end(), x), x);
        if ((T)v[p].size() >= 2 * S) split(p);
    }
    inline void remove(int x) {
        T p = find(x, 1, v.size());
        v[p].erase(lower_bound(v[p].begin(), v[p].end(), x));
        if (v[p].size() == 0) v.erase(v.begin() + p);
    }
    inline T get_rank(T x, T l, T r) {
        T ans = 0;
        for(size_t i = l; i <= r; i++) {
            if (v[i].back() >= x) {
                ans += lower_bound(v[i].begin(), v[i].end(), x) - v[i].begin();
                return ans + 1;
            }
            ans += v[i].size();
        }
        return 0;
    }
    inline T get_kth(T x, T l, T r) {
        for(int i = l; i <= r; i++) {
            if (v[i].size() >= x) return v[i][x - 1];
            x -= v[i].size();
        }
        return 0;
    }
    inline T get_pre(T x, T l, T r) {
        if(!x) return -2147483647;
        T p = find(x, l, r);
        auto pos = lower_bound(v[p].begin(), v[p].end(), x);
        if (pos == v[p].begin()) return v[p - 1].back();
        return *--pos;
    }
    inline T get_suf(T x, T l, T r) {
        if(!x) return 2147483647;
        T p = find(x + 1, l, r);
        auto pos = upper_bound(v[p].begin(), v[p].end(), x);
        if (pos == v[p].end()) return v[p + 1].front();
        return *pos;
    }
};

vector_tree <int> v;

signed main() {
    int q;
	read(n, q);
	S = (int)(sqrt(3.1415926 * n));
    for(int i = 1; i <= n; i++){
        int x;
        read(x);
        v.insert(x);
    }
	while (q--) {
		int op;
		read(op);
        switch (op) {
            case 1: {
                int l, r, k;
                read(l, r, k);
                write(v.get_rank(k, l, r), ' ');
                break;
            }
            case 2: {
                int l, r, k;
                read(l, r, k);
                write(v.get_kth(k, l, r), ' ');
                break;
            }
            case 3: {
                int pos, k;
                read(pos, k);
                v.remove(pos);
                v.insert(k);
                break;
            }
            case 4: {
                int l, r, k;
                read(l, r, k);
                write(v.get_pre(k, l, r), ' ');
                break;
            }
            case 5: {
                int l, r, k;
                read(l, r, k);
                write(v.get_suf(k, l, r), ' ');
            }
        }
	}
    system("pause");
	return 0;
}