Yuno And Claris
TimeLimit:20000MS MemoryLimit:524288KB
64-bit integer IO format:%I64d
未提交 | 登录后收藏
Problem Description
Yuno failed in a contest, so she was forced to wear JK dress.
Claris AKed in a 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,...,a_n$.
Because Yuno loves data structure, she invented $2$ kinds of operations :
$1\ l\ r\ x\ y$ : Change all the dresses in $a_l,a_{l+1},...,a_r$ with price $x$ to price $y$.
$2\ l\ r\ k $ : Yuno wants to wear the $k$-th cheapest dress in $a_l,a_{l+1},...,a_r$, please tell her the price of it.
Claris AKed in a 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,...,a_n$.
Because Yuno loves data structure, she invented $2$ kinds of operations :
$1\ l\ r\ x\ y$ : Change all the dresses in $a_l,a_{l+1},...,a_r$ with price $x$ to price $y$.
$2\ l\ r\ k $ : Yuno wants to wear the $k$-th cheapest dress in $a_l,a_{l+1},...,a_r$, please tell her the price of it.
Input
The first line of the input contains an integer $T(1\leq T\leq10)$, denoting the number of test cases.
In each test case, there are $2$ integers $n,m(1\leq n,m\leq 100000)$ in the first line, denoting the number of dresses and the number of operations.
In the next line, there are $n$ integers $a_1,a_2,...,a_n(1\leq a_i\leq n)$, denoting the price of each dress.
In the following $m$ lines, each line describes an operation.
If it is a modification, then it is in the format of ''$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 it is in the format of ''$2\ l\ r\ k$'', where $1\leq l\leq r\leq n$ and $1\leq k\leq r-l+1$.
In each test case, there are $2$ integers $n,m(1\leq n,m\leq 100000)$ in the first line, denoting the number of dresses and the number of operations.
In the next line, there are $n$ integers $a_1,a_2,...,a_n(1\leq a_i\leq n)$, denoting the price of each dress.
In the following $m$ lines, each line describes an operation.
If it is a modification, then it is in the format of ''$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 it is in the format of ''$2\ l\ r\ k$'', where $1\leq l\leq r\leq n$ and $1\leq k\leq r-l+1$.
Output
For each query, print a single line with an integer, denoting the answer.
SampleInput
1 3 3 2 3 3 2 1 3 1 1 1 3 3 1 2 1 3 2
SampleOutput
2 1