{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003ch3\u003e Read problems statements in \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/JAN15/mandarin/XRQRS.pdf\"\u003eMandarin Chinese \u003c/a\u003e and \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/JAN15/russian/XRQRS.pdf\"\u003eRussian\u003c/a\u003e.\u003c/h3\u003e\r\n\r\n\r\n\u003cp\u003e\r\nGiven an initially empty integer array (1-indexed) and some queries:\r\n\u003cul\u003e\r\n\u003cli\u003e\u003cb\u003eType 0\u003c/b\u003e: Add the integer number \u003cb\u003ex\u003c/b\u003e at the end of the array. \u003c/li\u003e\r\n\u003cli\u003e\u003cb\u003eType 1\u003c/b\u003e: On the interval \u003cb\u003eL..R\u003c/b\u003e find a number \u003cb\u003ey\u003c/b\u003e, to maximize (\u003cb\u003ex \u003ca href \u003d\"http://en.wikipedia.org/wiki/Bitwise_operation#XOR\"\u003exor\u003c/a\u003e y\u003c/b\u003e).\u003c/li\u003e\r\n\u003cli\u003e\u003cb\u003eType 2\u003c/b\u003e: Delete last \u003cb\u003ek\u003c/b\u003e numbers in the array\u003c/li\u003e\r\n\u003cli\u003e\u003cb\u003eType 3\u003c/b\u003e: On the interval \u003cb\u003eL..R\u003c/b\u003e, count the number of integers less than or equal to \u003cb\u003ex\u003c/b\u003e.\u003c/li\u003e\r\n\u003cli\u003e\u003cb\u003eType 4\u003c/b\u003e: On the interval \u003cb\u003eL..R\u003c/b\u003e, find the \u003cb\u003ek\u003csub\u003eth\u003c/sub\u003e\u003c/b\u003e smallest integer (\u003cb\u003ek\u003csub\u003eth\u003c/sub\u003e\u003c/b\u003e order statistic).\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003c/p\u003e\r\n\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cul\u003e\r\n\u003cli\u003eThe first line contains a single integer \u003cb\u003eM\u003c/b\u003e denoting number of queries. \u003c/li\u003e\r\n\u003cli\u003eThe following \u003cb\u003eM\u003c/b\u003e lines contain queries, form of queries is as follows.\u003c/li\u003e\r\n\u003cli\u003eQuery type 0 has the form \u003cb\u003e\"0 x\"\u003c/b\u003e. \u003c/li\u003e\r\n\u003cli\u003eQuery type 1 has the form \u003cb\u003e\"1 L R x\"\u003c/b\u003e. \u003c/li\u003e\r\n\u003cli\u003eQuery type 2 has the form \u003cb\u003e\"2 k\"\u003c/b\u003e. \u003c/li\u003e\r\n\u003cli\u003eQuery type 3 has the form \u003cb\u003e\"3 L R x\"\u003c/b\u003e. \u003c/li\u003e\r\n\u003cli\u003eQuery type 4 has the form \u003cb\u003e\"4 L R k\"\u003c/b\u003e. \u003c/li\u003e\r\n\u003c/ul\u003e\r\n\r\nNote that, there will be no invalid query in the input.\r\n\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003eFor each Query of type 1, 3 and 4 output the result in a single line.\u003c/p\u003e\r\n\r\n\u003ch3\u003eConstraints\u003c/h3\u003e\r\n\u003cul\u003e\u003c/ul\u003e\r\n\u003cli\u003eLet \u003cb\u003eN\u003c/b\u003e denote numbers of elements in before executing the query.\u003c/li\u003e\r\n\u003cli\u003e\u003cb\u003e1 ≤ M ≤ 5 * 10\u003csup\u003e5\u003c/sup\u003e\u003c/b\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cb\u003e1 ≤ x ≤ 5 * 10\u003csup\u003e5\u003csup\u003e\u003c/b\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cb\u003e1 ≤ L ≤ R ≤ N\u003c/b\u003e\u003c/li\u003e\r\n\u003cli\u003e For query type 2, \u003cb\u003e1 ≤ k ≤ N\t\u003c/b\u003e and for query type 4, \u003cb\u003ek ≤ R-L+1\u003c/b\u003e \u003c/li\u003e\r\n\r\n\u003ch3\u003eSubtasks\u003c/h3\u003e\r\n\u003cul\u003e\r\n\u003cli\u003eSubtask #1 (40 points): \u003cb\u003e1 ≤ M ≤ 5 * 10\u003csup\u003e4\u003c/sup\u003e\u003c/b\u003e \u003c/li\u003e\r\n\u003cli\u003eSubtask #2: (60 points): \u003cb\u003e1 ≤ M ≤ 5 * 10\u003csup\u003e5\u003c/sup\u003e\u003c/b\u003e \u003c/li\u003e\r\n\u003c/ul\u003e\r\n\r\n\u003ch3\u003eExample\u003c/h3\u003e\r\n\u003cpre\u003e\u003cb\u003eInput:\u003c/b\u003e\r\n10\r\n0 8\r\n4 1 1 1\r\n0 2\r\n1 2 2 7\r\n1 2 2 7\r\n0 1\r\n3 2 2 2\r\n1 1 2 3\r\n3 1 3 5\r\n0 6\r\n\r\n\u003cb\u003eOutput:\u003c/b\u003e\r\n8\r\n2\r\n2\r\n1\r\n8\r\n2\r\n\u003c/pre\u003e\r\n"}}]}