Yuno Gasai has given you a sequence $a$ of length $n$, and there are $m$ operations:

1. Change all occurrences of $x$ in the range $[l, r]$ to $y$.
2. Query the $k$-th smallest value in the range $[l, r]$.

Input

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

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

The following $m$ lines:

1 l r x y : Change all $x$ in the range $[l, r]$ to $y$.

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

Output

For each query, output a single integer representing the answer.

Examples

Input 1

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

Output 1

2
1

Subtasks

Idea: f321dd, Solution: f321dd&nzhtl1477, Code: nzhtl1477&Claris, Data: nzhtl1477&Juan_feng

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

By f321dd & nzhtl1477 & Claris