#P7477. [2017年杭电多校]Yuno And Claris

    ID: 7490 传统题 20000ms 256MiB 尝试: 2 已通过: 2 难度: 9 上传者: 标签>CF2600提高+/省选-根号分块普通并查集路径压缩按大小合并一维前缀和稀疏状态重置

[2017年杭电多校]Yuno And Claris

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 nn dresses, and put them in an array a1,a2,...,ana_1,a_2,...,a_n. Because Yuno loves data structure, she invented 22 kinds of operations : 1 l r x y1\ l\ r\ x\ y : Change all the dresses in al,al+1,...,ara_l,a_{l+1},...,a_r with price xx to price yy. 2 l r k2\ l\ r\ k : Yuno wants to wear the kk-th cheapest dress in al,al+1,...,ara_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≤T≤10)T(1\leq T\leq10), denoting the number of test cases. In each test case, there are 22 integers n,m(1≤n,m≤100000)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 nn integers a1,a2,...,an(1≤ai≤n)a_1,a_2,...,a_n(1\leq a_i\leq n), denoting the price of each dress. In the following mm lines, each line describes an operation. If it is a modification, then it is in the format of ''1 l r x y1\ l\ r\ x\ y'', where 1≤l≤r≤n1\leq l\leq r\leq n and 1≤x,y≤n1\leq x,y\leq n. If it is a query, then it is in the format of ''2 l r k2\ l\ r\ k'', where 1≤l≤r≤n1\leq l\leq r\leq n and 1≤k≤r−l+11\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