12240.Dynamic Rankings

The Company Dynamic Rankings has developed a new kind of computer that is no longer saisfied with the query like to simply find the k-thsmalest number of the given N numbers. They have developed a more powerful system such that for N numbers a[1], a[2],. . a[N], you canask it like: what is the k-th smallest number of a[l], a[i+1], .., a[j]? (For some i<=j,0<k<=j+1-i that you have given to it. More powerful, youcan even change the value of some al], and continue to query, all the same. Your task is to write a program for this computer, which Reads N numbers from the input (1 <= N <= 50,000)

• Processes M instructions of the input (1 <= M <= 10,000). These instructions incude querying the k-th smallest number of a[il, a[i+1]. ... a[j] and change some a[i] to t.

The first ine of the input is a single number X (0 < X <= 4), the number of the test cases of the input. Then X blocks each represent a singletest case. The first line of each block contains two integers N and M, representing N numbers and M instruction. itis followed by N lines. The (i+1)-hline represents the number a[i],. Then M lines that is in the following format Qijk or Cit It represents to query the k-th number of a[i], a[i+1],, a[j] and change some all to t, respectively. it is guaranteed that at any time of theoperation, Any number a[i] is a non-negative integer that is less than 1,000,000,000. There're NO breakline between two continuous test cases.

For each querying operation, output one integer to represent the result. (i.e. the k-th smallest number of a[i], a[i+1].., a[j]])There're NO breakline between two continuous test cases.