{"trustable":false,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003chtml\u003e\n \u003chead\u003e\u003c/head\u003e\n \u003cbody\u003e\n \u003cdiv id\u003d\"problem-body\"\u003e \n \u003ctable class\u003d\"problems\" width\u003d\"100%\"\u003e \n \u003ctbody\u003e \n \u003ctr class\u003d\"navigation\"\u003e \n \u003ctd width\u003d\"50%\"\u003e\u003ca \n \u003ctd width\u003d\"50%\"\u003e\u003ca \n \u003c/tr\u003e \n \u003c/tbody\u003e \n \u003c/table\u003e \n \u003cp\u003e\u003c/p\u003e \n \u003cp\u003e You are working for Macrohard 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 k-th order statistics in the array segment. \u003c/p\u003e \n \u003cp\u003e That is, given an array a[1 ... n] of different integer numbers, your program must answer a series of questions Q(i, j, k) in the form: \"What would be the k-th number in a[i ... j] segment, if this segment was sorted?\" \u003c/p\u003e \n \u003cp\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. \u003c/p\u003e \n \u003cp\u003e \u003c/p\u003e \n \u003ch3\u003eInput\u003c/h3\u003e \n \u003cp\u003e\u003c/p\u003e \n \u003cp\u003e The first line of the input contains n — the size of the array, and m — the number of questions to answer (1 ≤ n ≤ 100000, 1 ≤ m ≤ 5000). \u003c/p\u003e \n \u003cp\u003e The second line contains n different integer numbers not exceeding 10^9 by their absolute values — the array for which the answers should be given. \u003c/p\u003e \n \u003cp\u003e The following m lines contain question descriptions, each description consists of three numbers: i, j, and k (1 ≤ i ≤ j ≤ n, 1 ≤ k ≤ j - i + 1) and represents the question Q(i, j, k). \u003c/p\u003e \n \u003cpre\u003e\nSAMPLE INPUT\n7 3\n1 5 2 6 3 7 4\n2 5 3\n4 4 1\n1 7 3\n\n\u003c/pre\u003e \n \u003ch3\u003eOutput\u003c/h3\u003e \n \u003cpre\u003e \nFor each question output the answer to it — the k-th number in sorted \na[i ... j] segment. \n\nSAMPLE OUTPUT\n5\n6\n3\n\u003c/pre\u003e \n \u003cb\u003eNote : naive solution will not work!!!\u003c/b\u003e \n \u003c/div\u003e\n \u003c/body\u003e\n\u003c/html\u003e"}}]}