{"trustable":false,"sections":[{"title":"","value":{"format":"MD","content":"\u003ch3\u003e Read problems statements in \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/MAY16/mandarin/DISTNUM2.pdf\"\u003eMandarin Chinese\u003c/a\u003e, \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/MAY16/russian/DISTNUM2.pdf\"\u003eRussian\u003c/a\u003e and \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/MAY16/vietnamese/DISTNUM2.pdf\"\u003eVietnamese\u003c/a\u003e as well.\u003c/h3\u003e\n\n\n\u003cp\u003eYou are given an array \u003cb\u003eA\u003c/b\u003e consisting of \u003cb\u003eN\u003c/b\u003e positive integers. You have to answer \u003cb\u003eQ\u003c/b\u003e queries on it of following type: \u003c/p\u003e\n\u003cul\u003e\n\u003cli\u003e\u003cb\u003el r k\u003c/b\u003e : Let \u003cb\u003eS\u003c/b\u003e denote the \u003cem\u003esorted (in increasing order)\u003c/em\u003e set of elements of array \u003cb\u003eA\u003c/b\u003e with its indices between \u003cb\u003el\u003c/b\u003e and \u003cb\u003er\u003c/b\u003e. Note that set \u003cb\u003eS\u003c/b\u003e contains distinct elements (i.e. no duplicates).\nYou need to find \u003cb\u003ek\u003csup\u003eth\u003c/sup\u003e\u003c/b\u003e number in it. If such a number does not exist, i.e. the \u003cb\u003eS\u003c/b\u003e has less than \u003cb\u003ek\u003c/b\u003e elements, output -1.\u003c/li\u003e\n\u003c/ul\u003e\n\u003c/p\u003e\n\u003cp\u003eAll the indices in the queries are 1-based.\u003c/p\u003e\n\n\u003ch3\u003eInput\u003c/h3\u003e\n\u003cp\u003eThe first line of input contains two space separated integers \u003cb\u003eN\u003c/b\u003e and \u003cb\u003eQ\u003c/b\u003e denoting the number of elements in \u003cb\u003eA\u003c/b\u003e, and the number of queries, respectively. \n\u003c/p\u003e\n\u003cp\u003e\n\tThe second line of input contains \u003cb\u003eN\u003c/b\u003e space separated integers denoting the array \u003cb\u003eA\u003c/b\u003e. \n\u003c/p\u003e\n\u003cp\u003e\n\tEach of the next \u003cb\u003eQ\u003c/b\u003e lines contains five integers \u003cb\u003ea\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e, \u003cb\u003eb\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e, \u003cb\u003ec\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e, \u003cb\u003ed\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e, \u003cb\u003ek\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e. \n\tWe will generate \u003cb\u003el\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e, \u003cb\u003er\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e indices for this query as follows:\n\u003c/p\u003e\n\nLet answer for \u003cb\u003ei-1\u003csup\u003eth\u003c/sup\u003e\u003c/b\u003e query equal \u003cb\u003eans\u003csub\u003ei-1\u003c/sub\u003e\u003c/b\u003e. \nFor \u003cb\u003e0\u003csup\u003eth\u003c/sup\u003e\u003c/b\u003e query \u003cb\u003eans\u003csub\u003e0\u003c/sub\u003e\u003c/b\u003e \u003d 0. \nDefine \u003cb\u003el\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e \u003d (\u003cb\u003ea\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e x \u003cb\u003emax(ans\u003csub\u003ei - 1\u003c/sub\u003e, 0)\u003c/b\u003e + \u003cb\u003eb\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e) mod \u003cb\u003eN\u003c/b\u003e + 1, \n\u003cb\u003er\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e \u003d (\u003cb\u003ec\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e x \u003cb\u003emax(ans\u003csub\u003ei-1\u003c/sub\u003e, 0)\u003c/b\u003e + \u003cb\u003ed\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e) mod \u003cb\u003eN\u003c/b\u003e + 1. \nIf \u003cb\u003el\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e \u003e \u003cb\u003er\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e, then swap \u003cb\u003el\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e and \u003cb\u003er\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e.\n\n\n\u003ch3\u003eOutput\u003c/h3\u003e\n\u003cp\u003eFor each query, output the answer to the query in a single line. If such a number doesn\u0027t exist, output \u003cb\u003e-1\u003c/b\u003e. \u003c/p\u003e\n\n\u003ch3\u003eConstraints\u003c/h3\u003e\n\u003cul\u003e\n\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eN, Q\u003c/b\u003e ≤ \u003cb\u003e10\u003csup\u003e5\u003c/sup\u003e\u003c/b\u003e\u003c/li\u003e\n\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eA\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e ≤ \u003cb\u003e10\u003csup\u003e9\u003c/sup\u003e\u003c/b\u003e\u003c/li\u003e\n\u003cli\u003e\u003cb\u003e0\u003c/b\u003e ≤ \u003cb\u003ea\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e, \u003cb\u003eb\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e, \u003cb\u003ec\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e, \u003cb\u003ed\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e ≤ \u003cb\u003eN\u003c/b\u003e\u003c/li\u003e\n\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003el\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e ≤ \u003cb\u003er\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e ≤ \u003cb\u003eN\u003c/b\u003e\u003c/li\u003e\n\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003ek\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e ≤ \u003cb\u003eN\u003c/b\u003e \u003c/li\u003e\n\u003c/ul\u003e\n\n\u003ch3\u003eExample\u003c/h3\u003e\n\u003cpre\u003e\u003cb\u003eInput:\u003c/b\u003e\n4 4\n3 2 1 2\n0 1 0 3 2\n2 0 0 3 4\n1 2 1 3 2\n2 0 0 3 3\n\n\u003cb\u003eOutput:\u003c/b\u003e\n2\n-1\n2\n3\n\n\u003cb\u003eInput:\u003c/b\u003e\n10 10\n9 10 6 3 8 4 9 6 4 10\n0 2 0 9 3\n1 9 1 3 3\n1 8 1 0 3\n1 2 1 7 2\n1 6 1 2 3\n1 4 1 3 1\n1 6 1 6 1\n1 4 1 8 1\n1 9 1 3 3\n1 9 1 2 1\n\n\u003cb\u003eOutput:\u003c/b\u003e\n6\n9\n10\n4\n6\n3\n10\n4\n6\n4\n\u003c/pre\u003e\n\n\u003ch3\u003eSubtasks\u003c/h3\u003e\n\u003cul\u003e\n \u003cli\u003e\u003cb\u003eSubtask #1 (10 points) :\u003c/b\u003e \u003cb\u003eQ\u003c/b\u003e x \u003cb\u003eN \u003c/b\u003e≤ 10\u003csup\u003e7\u003c/sup\u003e\u003c/li\u003e\n \u003cli\u003e\u003cb\u003eSubtask #2 (20 points) :\u003c/b\u003e \u003cb\u003ek\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e \u003d 1\u003c/li\u003e\n \u003cli\u003e\u003cb\u003eSubtask #3 (30 points) :\u003c/b\u003e \u003cb\u003ea\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e \u003d 0, \u003cb\u003ec\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e \u003d 0\u003c/li\u003e\n \u003cli\u003e\u003cb\u003eSubtask #4 (40 points) :\u003c/b\u003e Original constraints\u003c/li\u003e\n\u003c/ul\u003e\n\n\u003ch3\u003eExplanation\u003c/h3\u003e\n\u003cp\u003e\u003cb\u003eExample #1:\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003e\u003cem\u003eQuery 1.\u003c/em\u003e Sorted set of elements : {1, 2}. Second number in this is 2.\u003c/p\u003e\n\u003cp\u003e\u003cem\u003eQuery 2.\u003c/em\u003e Sorted set of elements : {1, 2, 3}. Fourth number doesn\u0027t exist, hence answer is -1.\u003c/p\u003e\n\u003cp\u003e\u003cem\u003eQuery 3.\u003c/em\u003e Sorted set of elements : {1, 2}. Second number in this set is 2.\u003c/p\u003e\n\u003cp\u003e\u003cem\u003eQuery 4.\u003c/em\u003e Sorted set of elements : {1, 2, 3}. Third number in this set is 3.\u003c/p\u003e\n\n\u003caside style\u003d\u0027background: #f8f8f8;padding: 10px 15px;\u0027\u003e\u003cdiv\u003e\u003c/div\u003e\u003c/aside\u003e"}}]}