{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv\u003e\n You are working for \n \u003cspan\u003eMacrohard\u003c/span\u003e company in data structures department. After failing your previous task about key insertion you were asked to write a new data structure that would be able to return quickly \n \u003cspan\u003ek-th\u003c/span\u003e order statistics in the array segment.\n \u003cbr\u003e \n \u003cbr\u003e For example, consider the array a \u003d (1, 5, 2, 6, 3, 7, 4). Let the question be Q(2, 5, 3). The segment a[2...5] is (5, 2, 6, 3). If we sort this segment, we get (2, 3, 5, 6), the third number is 5, and therefore the answer to the question is 5.\n\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv\u003e\n The first line of the input file contains n --- the size of the array, and m --- the number of questions to answer (1 \u0026lt;\u003d n \u0026lt;\u003d 100 000, 1 \u0026lt;\u003d m \u0026lt;\u003d 5 000).\n \u003cbr\u003e The second line contains n different integer numbers not exceeding 10 \n \u003csup\u003e9\u003c/sup\u003e by their absolute values --- the array for which the answers should be given.\n \u003cbr\u003e The following m lines contain question descriptions, each description consists of three numbers: i, j, and k (1 \u0026lt;\u003d i \u0026lt;\u003d j \u0026lt;\u003d n, 1 \u0026lt;\u003d k \u0026lt;\u003d j - i + 1) and represents the question Q(i, j, k).\n\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cdiv\u003e\n For each question output the answer to it --- the \n \u003cspan\u003ek-th\u003c/span\u003e number in sorted a[i...j] segment.\n\u003c/div\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre\u003e\r\n7 3\r\n1 5 2 6 3 7 4\r\n2 5 3\r\n4 4 1\r\n1 7 3\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003e\r\n5\r\n6\r\n3\u003c/pre\u003e"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cdiv\u003e\n This problem has huge input,so please use c-style input(\n \u003cspan\u003escanf\u003c/span\u003e,\n \u003cspan\u003eprintf\u003c/span\u003e),or you may got time limit exceed.\n\u003c/div\u003e"}}]}