{"trustable":false,"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":"给定一个含有n个数的序列a[1],a[2],a[3]……a[n],程序必须回答这样的询问:\u003c/br\u003e\n对于给定的i,j,k,在a[i],a[i+1],a[i+2]……a[j]中第k小的数是多少(1≤k≤j-i+1)\u003c/br\u003e\n并且,你可以改变一些a[i]的值,改变后,程序还能针对改变后的a继续回答上面的问题。\n"}},{"title":"Input","value":{"format":"HTML","content":"第一个数表示数据组数。\n 第一行有两个正整数n(1≤n≤50000),m(1≤m≤10000)。分别表示序列的长度和指令的个数。\u003c/br\u003e第二行有n个数,表示a[1],a[2]……a[n],这些数都小于10^9。\u003c/br\u003e\n接下来的m行描述每条指令,每行的格式是下面两种格式中的一种。 Q i j k 或者 C i t \u003c/br\u003e\nQ i j k (i,j,k是数字,1≤i≤j≤n, 1≤k≤j-i+1)表示询问指令,询问a[i],a[i+1]……a[j]中第k小的数。\u003c/br\u003eC i t (1≤i≤n,0≤t≤10^9)表示把a[i]改变成为t。"}},{"title":"Output","value":{"format":"HTML","content":"\n于每一次询问,你都需要输出他的答案,每一个输出占单独的一行。"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003c/b\u003e\u003cbr\u003e \u003cbr\u003e 2\u003cbr\u003e 5 3\u003cbr\u003e 3 2 1 4 7\u003cbr\u003e Q 1 4 3\u003cbr\u003e C 2 6\u003cbr\u003e Q 2 5 3\u003cbr\u003e 5 3\u003cbr\u003e 3 2 1 4 7\u003cbr\u003e Q 1 4 3\u003cbr\u003e C 2 6\u003cbr\u003e Q 2 5 3\u003c/p\u003e \n \u003cp\u003e\u003cbr\u003e \u003cb"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003c/b\u003e\u003cbr\u003e \u003cbr\u003e 3\u003cbr\u003e 6\u003cbr\u003e 3\u003cbr\u003e 6\u003c/p\u003e \n \u003cp\u003e\u003cbr\u003e "}}]}