Given an array $A$ of $n$ integers, there are $q$ queries, each falling into one of two types:
- `1 l r x y`: For all $l \le i \le r$ where $A_i = x$, replace $A_i$ with $y$.
- `2 l r k`: Find the $k$-th smallest value in the range $A_l, A_{l+1}, ..., A_r$.
### Input
- The first line contains two integers $n, q$.
- The second line contains $n$ integers $A_i$.
- The next $q$ lines each contain a query in the specified format.
### Output
- Print an integer as the answer for each query of type `2`.
### Constraints
- $1 \le n, q, A_i, x, y \le 10^5$.
- $1 \le l \le r \le n$.
### Example
Input:
```
9 9
1 4 5 5 2 3 1 2 2
1 4 5 1 1
2 1 1 1
2 9 9 1
2 9 9 1
2 7 8 2
1 8 9 2 3
2 4 7 3
2 6 7 1
1 3 6 4 3
```
Output:
```
1
2
2
2
3
1
```
