{"trustable":true,"prependHtml":"\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 async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eSteve has an integer array $a$ of length $n$ (1-based). He assigned all the elements as zero at the beginning. After that, he made $m$ operations, each of which is to update an interval of $a$ with some value. You need to figure out $\\bigoplus_{i \u003d 1}^{n}{(i \\cdot a_i)}$ after all his operations are finished, where $\\bigoplus$ means the bitwise exclusive-OR operator.\u003cbr\u003eIn order to avoid huge input data, these operations are encrypted through some particular approach.\u003cbr\u003eThere are three unsigned 32-bit integers $X, Y$ and $Z$ which have initial values given by the input. A random number generator function is described as following, where $\\wedge$ means the bitwise exclusive-OR operator, $\u0026lt; \u0026lt;$ means the bitwise left shift operator and $\u0026gt; \u0026gt;$ means the bitwise right shift operator. Note that function would change the values of $X, Y$ and $Z$ after calling.\u003cbr\u003e\u003ccenter\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/d19af36f6580042d59feadb6b7511f75?v\u003d1714337030\"\u003e\u003c/center\u003e \u003cbr\u003eLet the $i$-th result value of calling the above function as $f_i$ $(i \u003d 1, 2, \\cdots, 3 m)$. The $i$-th operation of Steve is to update $a_j$ as $v_i$ if $a_j \u0026lt; v_i$ $(j \u003d l_i, l_i + 1, \\cdots, r_i)$, where\u003cbr\u003e$$\\begin{cases} l_i \u0026amp;\u003d \\min\\left((f_{3 i - 2} \\bmod n) + 1, (f_{3 i - 1} \\bmod n) + 1\\right) \\\\ r_i \u0026amp;\u003d \\max\\left((f_{3 i - 2} \\bmod n) + 1, (f_{3 i - 1} \\bmod n) + 1\\right) \\\\ v_i \u0026amp;\u003d f_{3 i} \\bmod 2^{30}\\end{cases} (i \u003d 1, 2, \\cdots, m).$$\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains one integer $T$, indicating the number of test cases.\u003cbr\u003eEach of the following $T$ lines describes a test case and contains five space-separated integers $n, m, X, Y$ and $Z$.\u003cbr\u003e$1 \\leq T \\leq 100$, $1 \\leq n \\leq 10^5$, $1 \\leq m \\leq 5 \\cdot 10^6$, $0 \\leq X, Y, Z \u0026lt; 2^{30}$.\u003cbr\u003eIt is guaranteed that the sum of $n$ in all the test cases does not exceed $10^6$ and the sum of $m$ in all the test cases does not exceed $5 \\cdot 10^7$."}},{"title":"Output","value":{"format":"HTML","content":"For each test case, output the answer in one line.\u003cbr\u003e"}},{"title":"Sample","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\u003e4\r\n1 10 100 1000 10000\r\n10 100 1000 10000 100000\r\n100 1000 10000 100000 1000000\r\n1000 10000 100000 1000000 10000000\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1031463378\r\n1446334207\r\n351511856\r\n47320301347\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cbr\u003eIn the first sample, a \u003d [1031463378] after all the operations.\u003cbr\u003eIn the second sample, a \u003d [1036205629, 1064909195, 1044643689, 1062944339, 1062944339, 1062944339, 1062944339, 1057472915, 1057472915, 1030626924] after all the operations.\u003cbr\u003e"}}]}