시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 512 MB | 5 | 1 | 1 | 50.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.
3 3 2 3 3 2 1 3 1 1 1 3 3 1 2 1 3 2
2 1