Background

So, Xiaoxue’s (pinyin) future belongs to Yuno’s~

Hmm... I know what your future will be like.

Listen up, I am Yuno Gasai.

Because Xiaoxue changed the future, the three of them could be together...

Why...

That makes me the bad guy...

I won’t stab.

Because... this is the future.

This... is my home.

Problem Description

Yuno Gasai gave you a sequence $a$ of length $n$, with $m$ operations.

1. Replace all occurrences of $x$ with $y$ within the interval $[l, r]$.
2. Query the $k$-th smallest value within the interval $[l, r]$.

Input Format

The first line contains two integers $n$ and $m$.

The second line contains $n$ integers representing the sequence $a$.

The next $m$ lines:

1 l r x y: Replace all $x$ in $[l, r]$ with $y$.

2 l r k: Query the $k$-th smallest value in $[l, r]$.

Output Format

For each query, output one integer as the answer.

3 3
2 3 3
2 1 3 1
1 1 3 3 1
2 1 3 2

2
1

Hint

Idea: f321dd, Solution: f321dd & nzhtl1477, Code: nzhtl1477 & Claris, testdata: nzhtl1477 & Juan_feng.

Constraints: $1 \le n, m, a_i \le 10^5$.

By f321dd & nzhtl1477 & Claris.

Translated by ChatGPT 5