{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eThe Company Dynamic Rankings has developed a new kind of computer that is no \n longer satisfied with the query like to simply find the k-th smallest number \n of the given N numbers. They have developed a more powerful system such that \n for N numbers a[1], a[2], ..., a[N], you can ask it like: what is the k-th smallest \n number of a[i], a[i+1], ..., a[j]? (For some i\u0026lt;\u003dj, 0\u0026lt;k\u0026lt;\u003dj+1-i that \n you have given to it). More powerful, you can even change the value of some \n a[i], and continue to query, all the same.\u003cbr\u003e\n \u003cbr\u003e\n Your task is to write a program for this computer, which\u003cbr\u003e\n \u003cbr\u003e\n - Reads N numbers from the input (1 \u0026lt;\u003d N \u0026lt;\u003d 50,000)\u003cbr\u003e\n \u003cbr\u003e\n - Processes M instructions of the input (1 \u0026lt;\u003d M \u0026lt;\u003d 10,000). These instructions \n include querying the k-th smallest number of a[i], a[i+1], ..., a[j] and change \n some a[i] to t.\u003c/p\u003e\n\u003cp\u003e\u003cbr\u003e\n \u003cb\u003eInput\u003c/b\u003e\u003cbr\u003e\n \u003cbr\u003e\n The first line of the input is a single number X (0 \u0026lt; X \u0026lt;\u003d 4), the number \n of the test cases of the input. Then X blocks each represent a single test case.\u003cbr\u003e\n \u003cbr\u003e\n The first line of each block contains two integers N and M, representing N numbers \n and M instruction. It is followed by N lines. The (i+1)-th line represents the \n number a[i]. Then M lines that is in the following format\u003cbr\u003e\n \u003cbr\u003e\n Q i j k or\u003cbr\u003e\n C i t\u003cbr\u003e\n \u003cbr\u003e\n It represents to query the k-th number of a[i], a[i+1], ..., a[j] and change \n some a[i] to t, respectively. It is guaranteed that at any time of the operation. \n Any number a[i] is a non-negative integer that is less than 1,000,000,000.\u003cbr\u003e\n \u003cbr\u003e\n There\u0027re NO breakline between two continuous test cases.\u003c/p\u003e\n\u003cp\u003e\u003cbr\u003e\n \u003cb\u003eOutput\u003c/b\u003e\u003cbr\u003e\n \u003cbr\u003e\n For each querying operation, output one integer to represent the result. (i.e. \n the k-th smallest number of a[i], a[i+1],..., a[j])\u003cbr\u003e\n \u003cbr\u003e\n There\u0027re NO breakline between two continuous test cases.\u003c/p\u003e\n\u003cp\u003e\u003cbr\u003e\n \u003cb\u003eSample Input\u003c/b\u003e\u003cbr\u003e\n \u003cbr\u003e\n 2\u003cbr\u003e\n 5 3\u003cbr\u003e\n 3 2 1 4 7\u003cbr\u003e\n Q 1 4 3\u003cbr\u003e\n C 2 6\u003cbr\u003e\n Q 2 5 3\u003cbr\u003e\n 5 3\u003cbr\u003e\n 3 2 1 4 7\u003cbr\u003e\n Q 1 4 3\u003cbr\u003e\n C 2 6\u003cbr\u003e\n Q 2 5 3\u003c/p\u003e\n\u003cp\u003e\u003cbr\u003e\n \u003cb\u003eSample Output\u003c/b\u003e\u003cbr\u003e\n \u003cbr\u003e\n 3\u003cbr\u003e\n 6\u003cbr\u003e\n 3\u003cbr\u003e\n 6\u003c/p\u003e\n\u003cp\u003e\u003cbr\u003e\n\u003ci\u003e\n (adviser)\u003c/i\u003e\u003cbr\u003e\n \u003cb\u003eSite:\u003c/b\u003e \u003ca href\u003d\"http://zhuzeyuan.hp.infoseek.co.jp/index.files/our_contest_20040619.htm\"\u003e\u003ci\u003ehttp://zhuzeyuan.hp.infoseek.co.jp/index.files/our_contest_20040619.htm\u003cbr\u003e\n \u003c/i\u003e\u003c/a\u003e\u003c/p\u003e\n"}}]}