#pragma GCC optimize("Ofast")
#pragma GCC target("avx")

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <assert.h>
#include <immintrin.h>

struct SqrtDecomposition {

    const int nGroups;

    float *gcnt;

    float *data;

    static const int gsize = 256;

    SqrtDecomposition(const int n) : nGroups((n + gsize - 1) / gsize) {
        gcnt = (float*)_mm_malloc(nGroups * sizeof(float), 32);
        data = (float*)_mm_malloc(n * sizeof(float), 32);
        std::fill(data, data + n, 0);
        std::fill(gcnt, gcnt + nGroups, 0);
    }
    
    void inc(int pos, int delta) {
        gcnt[pos / gsize] += (float)delta;
        data[pos] += (float)delta;
    }
    
    ~SqrtDecomposition() {
        _mm_free(data);
        _mm_free(gcnt);
    }
    
};

namespace Solution {
    
    const int NMAX = 100000;

    const int blockSize = 1024;
    
    const int MaxNBlocks = (NMAX + blockSize - 1) / blockSize;

    SqrtDecomposition* cntTillBorder[MaxNBlocks];
    
    SqrtDecomposition* zeroBuffer;
    
    float* arr;
    
    int n, nBlocks;
    
    void alloc(int n_) {
        n = n_;
        nBlocks = (n + blockSize - 1) / blockSize;
        arr = (float*)_mm_malloc(n * sizeof(float), 32);
        zeroBuffer = new SqrtDecomposition(n);
        for (int i = 0; i < nBlocks; ++i) {
            cntTillBorder[i] = new SqrtDecomposition(n);
        }
    }
    
    void free() {
        delete zeroBuffer;
        _mm_free(arr);
        for (int i = 0; i < nBlocks; ++i) {
            delete cntTillBorder[i];
        }
    }
    
    void precalc() {
        for (int i = 0; i < n; ++i) {
            int value = (int)arr[i];
            for (int b = i / blockSize; b < nBlocks; ++b) {
                cntTillBorder[b]->inc(value, +1);
            }
        }
    }
    
    void naiveUpdateItems(int begin, int after, float x, float y) {
        int cnt = 0;
        for (int i = begin; i < after; ++i) {
            cnt += (arr[i] == x);
            arr[i] = (arr[i] == x) ? y : arr[i];
        }
        for (int b = begin / blockSize; b < nBlocks; ++b) {
            cntTillBorder[b]->inc(int(x), -cnt);
            cntTillBorder[b]->inc(int(y), +cnt);
        }
    }
    
    void modify(int lt, int rt, float x, float y) {
        int bl = lt / blockSize;
        int br = rt / blockSize;
        if (bl == br) {
            naiveUpdateItems(lt, rt+1, x, y);
            return;
        }
        int changes = 0;
        for (int i = lt; i < (bl+1) * blockSize; ++i) {
            changes += (arr[i] == x);
            arr[i] = (arr[i] == x) ? y : arr[i];
        }
        cntTillBorder[bl]->inc(int(x), -changes);
        cntTillBorder[bl]->inc(int(y), +changes);
        
        __m256 vx = _mm256_set1_ps(x);
        __m256 vy = _mm256_set1_ps(y);
        
        for (int b = bl+1; b < br; ++b) {
            float *blockBegin = arr + b * blockSize;
            for (int i = 0; i + 31 < blockSize; i += 32) {
                uint32_t bitmask = 0;
                for (int j = 0; j < 32; j += 8) {
                    __m256 va = _mm256_load_ps(blockBegin + i + j);
                    __m256 rs = _mm256_cmp_ps(vx, va, _CMP_EQ_OQ);
                    bitmask = (bitmask << 8) | _mm256_movemask_ps(rs);
                    _mm256_maskstore_ps(blockBegin + i + j, _mm256_cvtps_epi32(rs), vy);
                }
                changes += __builtin_popcountll(bitmask);
            }
            cntTillBorder[b]->inc(int(x), -changes);
            cntTillBorder[b]->inc(int(y), +changes);
        }
        
        for (int i = br * blockSize; i <= rt; ++i) {
            changes += (arr[i] == x);
            arr[i] = (arr[i] == x) ? y : arr[i];
        }
        for (int b = br; b < nBlocks; ++b) {
            cntTillBorder[b]->inc(int(x), -changes);
            cntTillBorder[b]->inc(int(y), +changes);
        }
        
    }

    int nth_element(int lt, int rt, int k) {
        int bl = lt / blockSize;
        int br = rt / blockSize;
        SqrtDecomposition* arrLT = (bl == 0) ? zeroBuffer : cntTillBorder[bl-1];
        SqrtDecomposition* arrRT = cntTillBorder[br];
        for (int i = rt+1; i < std::min((br+1) * blockSize, n); ++i) { arrRT->inc((int)arr[i], -1); }
        for (int i = bl * blockSize; i < lt; ++i) { arrLT->inc((int)arr[i], +1); }
        int last = -1;
        static const int STEP = SqrtDecomposition::gsize;
        for (int g = 0; g < arrLT->nGroups; ++g) {
            int cnt = int(arrRT->gcnt[g] - arrLT->gcnt[g]);
            if (cnt >= k) { last = g * STEP - 1; break; }
            k -= cnt;
            last = g * STEP + STEP - 1;
        }
        
        int cnt = 0;
        while (cnt < k) { last++; cnt += int(arrRT->data[last] - arrLT->data[last]); }
        for (int i = bl * blockSize; i < lt; ++i) { arrLT->inc((int)arr[i], -1); }
        for (int i = rt+1; i < std::min((br+1) * blockSize, n); ++i) { arrRT->inc((int)arr[i], +1); }
        return last;
    }
}

char getChar() {
    static const int SIZE = 1 << 16;
    static char buffer[SIZE];
    static int pos = 0;
    static int size = 0;
    if (pos == size) {
        size = (int)fread(buffer, 1, SIZE, stdin),
        pos = 0;
    }
    if (pos == size) {
        return EOF;
    }
    return buffer[pos++];
}

template<typename T>
T getInt() {
    char c = '?';
    while (!(c == '-' || ('0' <= c && c <= '9'))) { c = getChar(); }
    bool pos = true;
    if (c == '-') { pos = false; c = getChar(); }
    T ret = 0;
    while ('0' <= c && c <= '9') { (ret *= 10) += (c - '0'); c = getChar(); }
    return pos ? ret : -ret;
}

void putChar(char c) {
    static const int SIZE = 1 << 16;
    static char buffer[SIZE];
    static int size = 0;
    if (size == SIZE || c == EOF) {
        fwrite(buffer, 1, size, stdout),
        size = 0;
    }
    if (c != EOF) { buffer[size++] = c; }
}

template<typename T>
void putInt(T value) {
    bool pos = true;
    if (value < 0) { pos = false; value = -value; }
    static char buf[24];
    int size = 0;
    do { buf[size++] = char(value % 10 + '0'); value /= 10; } while (value > 0);
    if (!pos) { buf[size++] = '-'; }
    while (size--) { putChar(buf[size]); }
}

#include <random>

void stressTest() {
    int n = 100000, q = 100000;
    Solution::alloc(n);
    for (int i = 0; i < n; ++i) {
        Solution::arr[i] = float(n-1);
    }
    Solution::precalc();
    std::mt19937 gen;
    std::uniform_int_distribution<int> dist(0, n-1);
    int last = n-1;
    uint64_t sum = 0;
    for (int id = 0; id < q; ++id) {
        if (id % 2 == 0) {
            int l = dist(gen);
            int r = dist(gen);
            if (l > r) { std::swap(l, r); }            
            auto res = Solution::nth_element(l, r, (r-l+1));
            assert(res == last);
            sum += res;
        } else {
            int x = last;
            int y = (n-1) + (n-2) - last;
            Solution::modify(0, n-1, x, y);
            last = y;
        }
    }
    assert(sum != 0);
    Solution::free();
    std::exit(0);
}

int main() {
    //stressTest();
    
    int n = getInt<int>(), q = getInt<int>();
    Solution::alloc(n);
    for (int i = 0; i < n; ++i) {
        Solution::arr[i] = (float)(getInt<int>()-1);
    }
    Solution::precalc();
    
    while (q--) {
        int t = getInt<int>();
        if (t == 1) {
            int lt = getInt<int>()-1, rt = getInt<int>()-1, x = getInt<int>()-1, y = getInt<int>()-1;
            Solution::modify(lt, rt, (float)x, (float)y);
        } else {
            int lt = getInt<int>()-1, rt = getInt<int>()-1, k = getInt<int>();
            putInt(Solution::nth_element(lt, rt, k)+1);
            putChar('\n');
            assert(t == 2);
        }
    }
    putChar(EOF);
    Solution::free();
    return 0;
}