시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 512 MB51150.000%

문제

Yuno failed in a contest, so she was forced to wear a JK dress. Claris won the contest, so she bought some JK dresses for Yuno to wear. Each dress has a price. Because Claris has lots of money, she bought $n$ dresses and put them in an array $a_1, a_2, \ldots, a_n$.

Because Yuno loves data structures, she invented two kinds of operations:

  • "1 l r x y": For all the dresses in $a_l, a_{l+1}, \ldots, a_r$, if the price of a dress is $x$, change its price to $y$.
  • "2 l r k": Yuno wants to wear the $k$-th cheapest dress from $a_l, a_{l+1}, \ldots, a_r$, so tell her the price of this dress.

입력

The first line of the input contains two integers $n$ and $m$: the number of dresses and the number of operations ($1 \leq n, m \leq 10^5$). The second line contains $n$ integers $a_1, a_2, \ldots, a_n$: the prices of the dresses ($1 \leq a_i \leq n$). Each of the following $m$ lines describes an operation. If it is a modification, then the line is formatted as "1 l r x y", where $1 \leq l \leq r \leq n$ and $1 \leq x, y \leq n$. If it is a query, then the line is formatted as "2 l r k", where $1 \leq l \leq r \leq n$ and $1 \leq k \leq r - l + 1$.

출력

For each query, print a single line with a single integer: the answer to the query.

예제 입력 1

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

예제 출력 1

2
1