Yuno And Claris

Time Limit: 40000/20000 MS (Java/Others)

Memory Limit: 524288/524288 K (Java/Others)

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.

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$.

Output

For each query, print a single line with an integer, denoting the answer.

Sample Input

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

Sample Output

2 1

Hint

liuyiding

Source

2017 Multi-University Training Contest - Te

提交代码