{"raw_statement":[{"iden":"statement","content":"Chitanda owns a farm with $n$ apple trees on it, labeled by $1, 2, \\\\dots, n$, the $i$-th apple tree has $a_i$ apples. There are $n -1$ bidirectional roads connecting them. For all $i > 1$, an apple tree number $i$ is connected by a road to the apple tree number $floor.l frac(i, 2) floor.r$. So the map of the farm is also like a tree.\n\nApple business is booming. There are $m$ requests, labeled by $1, 2, \\\\dots, m$. For the $i$-th request, Chitanda can sell the customer at most $c_i$ apples, and the customer will pay $w_i$ dollars for each apple. Unfortunately, different customers have different preferences. Specifically, for the $i$-th request, the customer will give two integers $u_i$ and $v_i$, denoting he only accepts apples from trees on the shortest path from the $u_i$-th apple tree to the $v_i$-th apple tree on the map(include $u_i$ and $v_i$).\n\nAssume the root of the map is the $1$-th apple tree. It is amazing that $u_i$ is always $v_i$'s ancestor or $u_i = v_i$.\n\nThe farm may not be able to sell $c_i$ apples to each customer. Please write a program to help Chitanda sell apples that will maximize his profits.\n\nThe first line of the input contains an integer $T (1 <= T <= 1000)$, denoting the number of test cases.\n\nIn each test case, there are two integers $n, m (1 <= n, m <= 100000)$ in the first line, denoting the number of apple trees and requests.\n\nIn the second line, there are $n$ integers $a_1, a_2,..., a_n (1 <= a_i <= 10^9)$, denoting the number of apples on each apple tree.\n\nFor the next $m$ lines, each line contains four integers $u_i, v_i, c_i, w_i (1 <= u_i, v_i <= n, 1 <= c_i <= 10^9, 1 <= w_i <= 10^4)$, denoting each request. It is guaranteed that $u_i$ is $v_i$'s ancestor or $u_i = v_i$.\n\nIt is guaranteed that $sum n <= 10^6$ and $sum m <= 10^6$.\n\nFor each test case, print a single line containing an integer, denoting the maximum profits.\n\n"},{"iden":"input","content":"The first line of the input contains an integer $T (1 <= T <= 1000)$, denoting the number of test cases.In each test case, there are two integers $n, m (1 <= n, m <= 100000)$ in the first line, denoting the number of apple trees and requests.In the second line, there are $n$ integers $a_1, a_2,..., a_n (1 <= a_i <= 10^9)$, denoting the number of apples on each apple tree.For the next $m$ lines, each line contains four integers $u_i, v_i, c_i, w_i (1 <= u_i, v_i <= n, 1 <= c_i <= 10^9, 1 <= w_i <= 10^4)$, denoting each request. It is guaranteed that $u_i$ is $v_i$'s ancestor or $u_i = v_i$.It is guaranteed that $sum n <= 10^6$ and $sum m <= 10^6$."},{"iden":"output","content":"For each test case, print a single line containing an integer, denoting the maximum profits."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $:  \n- Let $ n_k \\in \\mathbb{Z} $ be the number of operations.  \n- Let $ p_k, q_k, m_k \\in \\mathbb{Z} $, and $ SA_k, SB_k, SC_k \\in \\mathbb{Z} $ be seed parameters.  \n- Define the pseudorandom generator function $ \\text{rng61}_k : \\mathbb{Z} \\to \\mathbb{Z} $ as:  \n  $$\n  \\text{rng61}_k() = \n  \\begin{cases}\n  SA_k \\gets SA_k \\oplus (SA_k \\ll 16) \\\\\n  SA_k \\gets SA_k \\oplus (SA_k \\gg 5) \\\\\n  SA_k \\gets SA_k \\oplus (SA_k \\ll 1) \\\\\n  t \\gets SA_k \\\\\n  SA_k \\gets SB_k \\\\\n  SB_k \\gets SC_k \\\\\n  SC_k \\gets SC_k \\oplus t \\oplus SA_k \\\\\n  \\text{return } SC_k\n  \\end{cases}\n  $$  \n- Define the sequence of operations $ O_k = (o_{k,1}, \\dots, o_{k,n_k}) $, where for each $ i \\in \\{1, \\dots, n_k\\} $:  \n  $$\n  o_{k,i} = \n  \\begin{cases}\n  \\text{PUSH}(v) & \\text{if } \\text{rng61}_k() \\bmod (p_k + q_k) < p_k, \\text{ where } v = \\text{rng61}_k() \\bmod m_k + 1 \\\\\n  \\text{POP}() & \\text{otherwise}\n  \\end{cases}\n  $$  \n- Let $ S_k = (s_{k,1}, s_{k,2}, \\dots) $ be the stack state after each operation, initialized as empty.  \n- Let $ a_{k,i} \\in \\mathbb{Z}_{\\ge 0} $ be the maximum element in $ S_k $ after the $ i $-th operation, or $ 0 $ if the stack is empty.  \n\n**Constraints**  \n1. $ 1 \\le T \\le 50 $  \n2. $ 1 \\le n_k \\le 5 \\times 10^6 $  \n3. $ 1 \\le p_k, q_k, m_k \\le 10^9 $  \n4. $ 10^4 \\le SA_k, SB_k, SC_k \\le 10^6 $  \n\n**Objective**  \nFor each test case $ k $, compute:  \n$$\ny_k = \\bigoplus_{i=1}^{n_k} (i \\cdot a_{k,i})\n$$  \nwhere $ \\oplus $ denotes bitwise XOR.  \nOutput: `Case #x: y` for each test case $ x = k $.","simple_statement":"Implement a stack that supports push, pop, and tracking the current maximum. Generate operations using given RNG. After each operation, record the max (or 0 if empty). Output XOR of all (i * current_max) for i from 1 to n.","has_page_source":false}