{"raw_statement":[{"iden":"statement","content":"*This is the easy version of the problem. The changes in this version are highlighted in bold characters*.\n\nYugandhar have an undirected graph containing $n$ nodes numbered $1, 2,...., n$. Initially there are $0$ edges i.e., there are total $n$ connected components in the graph. He has a freedom to add exactly $k$ undirected edges in this graph, each edge can be added between $u$ and $v$ if and only if $v$ = $u + 1$. Note that he can add multiple edges between two nodes. \n\nAfter giving this graph to wuhudsm, he will observe the following $m$ requirements and reward him coins :\n\nSo Please tell him the optimal way to select these $k$ edges to get maximum number of coins.\n\nAditionally, help him for $q$ queries.\n\nEach test contains multiple test cases. The first line contains the number of test cases $t$ ($1 <= t <= 10^4$). The description of the test cases follows.\n\nThe first line of test case contains three integers $n, m, q$ ($2 <= n <= bold(2 dot.op 10^3)$, $1 <= m <= bold(2 dot.op 10^3)$, $1 <= q <= 10^6$) — the number of nodes in graph, the number of requirements and the number of queries.\n\nNext $m$ lines of each test case contains three space separated integers $x_i, y_i, c_i$ ($1 <= x_i, y_i <= n$, $x_i ≠ y_i$, $1 <= c_i <= 10^9$).\n\nNext $q$ lines of each test case contains a single integer $k_i$ ($1 <= k_i <= 10^9$) — the total number of edges needed to add in graph.\n\nIt is guaranteed that the sum of $n$ and sum of $m$ over all test cases doesn't exceed $bold(2 dot.op 10^3)$.\n\nIt is guaranteed that the sum of $q$ over all test cases doesn't exceed $10^6$. \n\nFor each test case print $q$ integers — the maximum number of coins he can get if he choose exactly $k_i$ edges optimally.\n\n"},{"iden":"input","content":"Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 <= t <= 10^4$). The description of the test cases follows.The first line of test case contains three integers $n, m, q$ ($2 <= n <= bold(2 dot.op 10^3)$, $1 <= m <= bold(2 dot.op 10^3)$, $1 <= q <= 10^6$) — the number of nodes in graph, the number of requirements and the number of queries.Next $m$ lines of each test case contains three space separated integers $x_i, y_i, c_i$ ($1 <= x_i, y_i <= n$, $x_i ≠ y_i$, $1 <= c_i <= 10^9$).Next $q$ lines of each test case contains a single integer $k_i$ ($1 <= k_i <= 10^9$) — the total number of edges needed to add in graph.It is guaranteed that the sum of $n$ and sum of $m$ over all test cases doesn't exceed $bold(2 dot.op 10^3)$.It is guaranteed that the sum of $q$ over all test cases doesn't exceed $10^6$. "},{"iden":"output","content":"For each test case print $q$ integers — the maximum number of coins he can get if he choose exactly $k_i$ edges optimally."}],"translated_statement":[{"iden":"statement","content":"*这是该问题的简单版本。唯一的区别是时间限制和内存限制。*\n\n给定一个大小为 $n$ 的数组 $a$。\n\n你执行以下操作：\n\n记 $s_i = a_{l_i} | a_{l_{i + 1}} | ... | a_{r_i}$。这里 $|$ 表示按位或。\n\n求 $Σ_{i = 1}^k (-1)^{i + 1} * s_i$ 的最大值。\n\n输入的第一行包含一个整数 $t (1 lt.eq t lt.eq 10^6)$，表示测试用例的数量。\n\n每个测试用例由多行输入组成。\n\n每个测试用例的第一行包含一个整数 $n (1 lt.eq n lt.eq 10^6)$。\n\n接下来的行包含 $n$ 个用空格分隔的整数：$a_1$，$a_2$，...，$a_n$ $(0 lt.eq a_i < 2^{30})$。\n\n所有测试用例的 $n$ 之和不超过 $10^6$。\n\n对于每个测试用例，在新行上输出 —— $Σ_{i = 1}^k (-1)^{i + 1} * s_i$ 的最大值。\n\n测试用例 $1$：\n\n选择 $k = 3, [ l_1, r_1 ] = [ 1, 1 ], [ l_2, r_2 ] = [ 2, 2 ], [ l_3, r_3 ] = [ 3, 3 ]$。\n\n我们得到 $s_1 = 2, s_2 = 1, s_3 = 2$。答案是 $s_1 - s_2 + s_3 = 2 - 1 + 2 = 3$。\n\n测试用例 $2$：\n\n选择 $k = 1, [ l_1, r_1 ] = [ 1, 6 ]$。\n\n我们得到 $s_1 = 6$。答案是 $s_1 = 6$。\n\n"},{"iden":"input","content":"输入的第一行包含一个整数 $t (1 lt.eq t lt.eq 10^6)$，表示测试用例的数量。每个测试用例由多行输入组成。每个测试用例的第一行包含一个整数 $n (1 lt.eq n lt.eq 10^6)$。接下来的行包含 $n$ 个用空格分隔的整数：$a_1$，$a_2$，...，$a_n$ $(0 lt.eq a_i < 2^{30})$。所有测试用例的 $n$ 之和不超过 $10^6$。"},{"iden":"output","content":"对于每个测试用例，在新行上输出 —— $Σ_{i = 1}^k (-1)^{i + 1} * s_i$ 的最大值。"},{"iden":"note","content":"测试用例 $1$：选择 $k = 3, [ l_1, r_1 ] = [ 1, 1 ], [ l_2, r_2 ] = [ 2, 2 ], [ l_3, r_3 ] = [ 3, 3 ]$。我们得到 $s_1 = 2, s_2 = 1, s_3 = 2$。答案是 $s_1 - s_2 + s_3 = 2 - 1 + 2 = 3$。测试用例 $2$：选择 $k = 1, [ l_1, r_1 ] = [ 1, 6 ]$。我们得到 $s_1 = 6$。答案是 $s_1 = 6$。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ t \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case:  \n- Let $ n \\in \\mathbb{Z} $ denote the size of the array.  \n- Let $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of non-negative integers, where $ 0 \\le a_i < 2^{30} $.  \n- A *partition* of $ A $ into $ k $ contiguous non-empty subarrays is defined by indices $ 1 = l_1 \\le r_1 < l_2 \\le r_2 < \\dots < l_k \\le r_k = n $.  \n- For each subarray $ [l_i, r_i] $, define $ s_i = \\bigvee_{j=l_i}^{r_i} a_j $ (bitwise OR over the subarray).  \n\n**Constraints**  \n1. $ 1 \\le t \\le 10^6 $  \n2. $ 1 \\le n \\le 10^6 $ per test case  \n3. $ \\sum_{\\text{all test cases}} n \\le 10^6 $  \n4. $ 0 \\le a_i < 2^{30} $ for all $ i $  \n\n**Objective**  \nFor each test case, maximize the alternating sum:  \n$$\n\\max_{k \\ge 1} \\sum_{i=1}^{k} (-1)^{i+1} s_i\n$$  \nover all possible partitions of $ A $ into $ k $ contiguous non-empty subarrays.","simple_statement":null,"has_page_source":false}