{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eTo enter the spaceship security system, the astromechanical droid R2-D2 uses a secret cryptographic algorithm, one step of which solves the following problem:\u003c/p\u003e\u003cp\u003eConsider a thin paper strip with \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e \u003d 2\u003csup class\u003d\"upper-index\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/sup\u003e\u003c/span\u003e cells located in one row. The cells are numbered \u003cspan class\u003d\"tex-span\"\u003e0\u003c/span\u003e through \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e - 1\u003c/span\u003e. Fold the strip in half, the right half under the left one, so that the cell numbered \u003cspan class\u003d\"tex-span\"\u003e2\u003csup class\u003d\"upper-index\"\u003e\u003ci\u003ek\u003c/i\u003e - 1\u003c/sup\u003e - \u003ci\u003ej\u003c/i\u003e\u003c/span\u003e will be above the cell numbered \u003cspan class\u003d\"tex-span\"\u003e2\u003csup class\u003d\"upper-index\"\u003e\u003ci\u003ek\u003c/i\u003e - 1\u003c/sup\u003e + \u003ci\u003ej\u003c/i\u003e - 1\u003c/span\u003e for all \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/span\u003e from \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e to \u003cspan class\u003d\"tex-span\"\u003e2\u003csup class\u003d\"upper-index\"\u003e\u003ci\u003ek\u003c/i\u003e - 1\u003c/sup\u003e\u003c/span\u003e. Then fold the resulting strip, which has how length \u003cspan class\u003d\"tex-span\"\u003e2\u003csup class\u003d\"upper-index\"\u003e\u003ci\u003ek\u003c/i\u003e - 1\u003c/sup\u003e\u003c/span\u003e, again and again in the same way until the length of the strip is one. In the resulting folded strip, the cells are placed above each other in some order. Let the sequence \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e0\u003c/sub\u003e, \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, ..., \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003en\u003c/i\u003e - 1\u003c/sub\u003e\u003c/span\u003e be the numbers of the cells from top to bottom.\u003c/p\u003e\u003cp\u003eWhen the droid connects to the spaceship system, it is given an integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e, and after that, it is asked several queries to get verified. Each query is a segment \u003cspan class\u003d\"tex-span\"\u003e[\u003ci\u003el\u003c/i\u003e, \u003ci\u003er\u003c/i\u003e]\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e0 ≤ \u003ci\u003el\u003c/i\u003e ≤ \u003ci\u003er\u003c/i\u003e \u0026lt; \u003ci\u003en\u003c/i\u003e\u003c/span\u003e) for which the droid must compute the following expression, in which operations \u003cspan class\u003d\"tex-span\"\u003e + \u003c/span\u003e and \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/f2fe3e60ef565744bf61ec18d7bc2fbe?v\u003d1714317115\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e alternate: \u003c/p\u003e\u003ccenter class\u003d\"tex-equation\"\u003e\u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/97142cf326b2c2bc72a60e8eae9eb84c?v\u003d1714317115\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e\u003c/center\u003e Additional care must be taken since operation \u003cspan class\u003d\"tex-span\"\u003e + \u003c/span\u003e has higher priority than \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/f2fe3e60ef565744bf61ec18d7bc2fbe?v\u003d1714317115\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e if \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003el\u003c/i\u003e\u003c/span\u003e is even, and operation \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/f2fe3e60ef565744bf61ec18d7bc2fbe?v\u003d1714317115\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e has higher priority than \u003cspan class\u003d\"tex-span\"\u003e + \u003c/span\u003e otherwise. If the droid doesn\u0027t answer correctly these queries in one second, he is revealed.\u003cp\u003eR2-D2 argued with C-3PO that the latter couldn\u0027t solve this problem. C-3PO is a protocol droid, it knows six million forms of communication, but nothing about cryptography. Help him to solve the problem in order to surprise R2-D2.\u003c/p\u003e\u003cp\u003eIn order to emulate a security system, R2-D2 suggested an algorithm for choosing the segments \u003cspan class\u003d\"tex-span\"\u003e[\u003ci\u003el\u003c/i\u003e, \u003ci\u003er\u003c/i\u003e]\u003c/span\u003e. He also suggested to check only the results of hashing \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eF\u003c/i\u003e(\u003ci\u003el\u003c/i\u003e, \u003ci\u003er\u003c/i\u003e)\u003c/span\u003e, but not the values \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eF\u003c/i\u003e(\u003ci\u003el\u003c/i\u003e, \u003ci\u003er\u003c/i\u003e)\u003c/span\u003e themselves. Let the queries be numbered \u003cspan class\u003d\"tex-span\"\u003e0\u003c/span\u003e through \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e - 1\u003c/span\u003e. Then these values are computed as follows:\u003c/p\u003e\u003cul\u003e \u003cli\u003e \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/42f6bc903c3b6932eebf382489fd84b9?v\u003d1714317115\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e; \u003c/li\u003e\u003cli\u003e \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/5210268482bf870c948ab53eda9cf190?v\u003d1714317115\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e; \u003c/li\u003e\u003cli\u003e \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/7cfa893e0fc5e90924b0ae403617cf3c?v\u003d1714317115\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e. \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eHere, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eh\u003c/i\u003e\u003c/span\u003e is the value of the hash function, and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eh\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e0\u003c/sub\u003e \u003d 0\u003c/span\u003e. Your task is to compute the final hash value \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eh\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line of input contains an integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e0 ≤ \u003ci\u003ek\u003c/i\u003e ≤ 30\u003c/span\u003e).\u003c/p\u003e\u003cp\u003eThe second line contains three integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003el\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e0\u003c/sub\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003er\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e0\u003c/sub\u003e\u003c/span\u003e: the number of queries and the bounds of the initial query (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003em\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e7\u003c/sup\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e0 ≤ \u003ci\u003el\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e0\u003c/sub\u003e ≤ \u003ci\u003er\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e0\u003c/sub\u003e \u0026lt; \u003ci\u003en\u003c/i\u003e\u003c/span\u003e).\u003c/p\u003e\u003cp\u003eThe third line contains three integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eb\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003c/span\u003e: the parameters of the generating algorithm (\u003cspan class\u003d\"tex-span\"\u003e0 ≤ \u003ci\u003ea\u003c/i\u003e, \u003ci\u003eb\u003c/i\u003e, \u003ci\u003ec\u003c/i\u003e \u0026lt; 2\u003csup class\u003d\"upper-index\"\u003e30\u003c/sup\u003e\u003c/span\u003e).\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003ePrint one integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eh\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e: the value of the hash function after processing all queries.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\n1 2 6\n3 4 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e7\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\n709193 4 5\n273035200 65685838 991992535\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e156951996\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eOperation \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/f2fe3e60ef565744bf61ec18d7bc2fbe?v\u003d1714317115\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e means exclusive or.\u003c/p\u003e\u003cp\u003eThe results of operations with higher priority must be computed earlier. Operations with the same priority must be processed in the order from left to right.\u003c/p\u003e\u003cp\u003eA strip of length \u003cspan class\u003d\"tex-span\"\u003e2\u003csup class\u003d\"upper-index\"\u003e3\u003c/sup\u003e \u003d 8\u003c/span\u003e folds like in the picture.\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/0d5f45c81f35c8b9055737fab03d6664?v\u003d1714317115\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e"}}]}