Yuno And Claris

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.

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

Source

2017 Multi-University Training Contest - Team 4

https://acm.hdu.edu.cn/showproblem.php?pid=6079