{"problem":{"name":"G. Glad You Came","description":{"content":"Steve 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","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10211G"},"statements":[{"statement_type":"Markdown","content":"Steve 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  after all his operations are finished, where  means the bitwise exclusive-OR operator.\n\nIn order to avoid huge input data, these operations are encrypted through some particular approach.\n\nThere 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  means the bitwise exclusive-OR operator,  <  <  means the bitwise left shift operator and  >  >  means the bitwise right shift operator. Note that function would change the values of X, Y and Z after calling.\n\nLet the i-th result value of calling the above function as fi (i = 1, 2, ..., 3m). The i-th operation of Steve is to update aj as vi if aj < vi (j = li, li + 1, ..., ri), where\n\nThe first line contains one integer T, indicating the number of test cases.\n\nEach of the following T lines describes a test case and contains five space-separated integers n, m, X, Y and Z.\n\n1 ≤ T ≤ 100, 1 ≤ n ≤ 105, 1 ≤ m ≤ 5·106, 0 ≤ X, Y, Z < 230.\n\nIt is guaranteed that the sum of n in all the test cases does not exceed 106 and the sum of m in all the test cases does not exceed 5·107.\n\nFor each test case, output the answer in one line.\n\nIn the first sample, a = [1031463378] after all the operations.\n\nIn the second sample, a = [1036205629,  1064909195,  1044643689,  1062944339,  1062944339,  1062944339,  1062944339,  1057472915,  1057472915,  1030626924] after all the operations.\n\n## Input\n\nThe first line contains one integer T, indicating the number of test cases.Each of the following T lines describes a test case and contains five space-separated integers n, m, X, Y and Z.1 ≤ T ≤ 100, 1 ≤ n ≤ 105, 1 ≤ m ≤ 5·106, 0 ≤ X, Y, Z < 230.It is guaranteed that the sum of n in all the test cases does not exceed 106 and the sum of m in all the test cases does not exceed 5·107.\n\n## Output\n\nFor each test case, output the answer in one line.\n\n[samples]\n\n## Note\n\nIn the first sample, a = [1031463378] after all the operations.In the second sample, a = [1036205629,  1064909195,  1044643689,  1062944339,  1062944339,  1062944339,  1062944339,  1057472915,  1057472915,  1030626924] after all the operations.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case:  \n- Let $ n \\in \\mathbb{Z} $ be the length of the array $ a = (a_1, \\dots, a_n) $, initialized to all zeros.  \n- Let $ m \\in \\mathbb{Z} $ be the number of operations.  \n- Let $ X, Y, Z \\in \\mathbb{U}_{32} $ be initial 32-bit unsigned integers.  \n\nDefine the RNG function:  \n$$\n\\text{rng}() := \\left( X \\leftarrow (X \\oplus (X \\ll 11)) \\oplus (X \\gg 8), \\quad Y \\leftarrow (Y \\oplus (Y \\gg 19)) \\oplus (Y \\ll 16), \\quad Z \\leftarrow (Z \\oplus (Z \\oplus (Z \\ll 10)) \\oplus (Z \\gg 6)), \\quad f_i = X \\oplus Y \\oplus Z \\right)\n$$  \nThis function updates $ X, Y, Z $ and returns $ f_i $, the $ i $-th random value.  \n\nLet $ f_1, f_2, \\dots, f_{3m} $ be the first $ 3m $ outputs of `rng()` in sequence.  \n\nFor the $ i $-th operation ($ i \\in \\{1, \\dots, m\\} $):  \n- $ l_i = (f_{3i-2} \\bmod n) + 1 $  \n- $ r_i = (f_{3i-1} \\bmod n) + 1 $  \n- $ v_i = f_{3i} $  \n- If $ l_i > r_i $, swap $ l_i $ and $ r_i $.  \n- For each $ j \\in \\{l_i, l_i+1, \\dots, r_i\\} $, update:  \n  $$\n  a_j \\leftarrow \\begin{cases} \n  v_i & \\text{if } a_j < v_i \\\\\n  a_j & \\text{otherwise}\n  \\end{cases}\n  $$\n\n**Constraints**  \n1. $ 1 \\le T \\le 100 $  \n2. $ 1 \\le n \\le 10^5 $, $ 1 \\le m \\le 5 \\cdot 10^6 $  \n3. $ 0 \\le X, Y, Z < 2^{30} $  \n4. $ \\sum_{\\text{test cases}} n \\le 10^6 $  \n5. $ \\sum_{\\text{test cases}} m \\le 5 \\cdot 10^7 $  \n\n**Objective**  \nAfter all operations, compute:  \n$$\n\\bigoplus_{j=1}^{n} a_j\n$$  \nwhere $ \\oplus $ denotes bitwise XOR.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10211G","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}