CF1744B.Even-Odd Increments

You are given $n$ of integers $a_1, a_2, \ldots, a_n$. Process $q$ queries of two types:

• query of the form "0 $x_j$": add the value $x_j$ to all even elements of the array $a$,
• query of the form "1 $x_j$": add the value $x_j$ to all odd elements of the array $a$.

Note that when processing the query, we look specifically at the odd/even value of $a_i$, not its index.

After processing each query, print the sum of the elements of the array $a$.

Please note that the answer for some test cases won't fit into 32-bit integer type, so you should use at least 64-bit integer type in your programming language (like long long for C++).

给你 $n$ 个整数 $a_1, a_2, \ldots, a_n$。你需要处理 $q$ 个查询，查询分为两类：

• 形如 “0 $x_j$” 的查询：将值 $x_j$ 加到数组 $a$ 中所有偶数元素上；
• 形如 “1 $x_j$” 的查询：将值 $x_j$ 加到数组 $a$ 中所有奇数元素上。

注意：在处理查询时，我们依据的是元素 $a_i$ 本身的值的奇偶性，而非其下标 $i$ 的奇偶性。

每次查询处理完毕后，请输出此时数组 $a$ 中所有元素的和。

请注意：某些测试用例的答案可能超出 32 位整数范围，因此你应至少使用 64 位整数类型（例如 C++ 中的 long long）。

The first line of the input contains an integer $t$ $(1 \leq t \leq 10^4$) — the number of test cases.

The descriptions of the test cases follow.

The first line of each test case contains two integers $n$ and $q$ ($1 \leq n$, $q \leq 10^5$) — the length of array $a$ and the number of queries.

The second line of each test case contains exactly $n$ integers: $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$) — elements of the array $a$.

The following $q$ lines contain queries as two integers $type_j$ and $x_j$ $(0 \leq type_j \leq 1$, $1 \leq x_j \leq 10^4$).

It is guaranteed that the sum of values $n$ over all test cases in a test does not exceed $10^5$. Similarly, the sum of values $q$ over all test cases does not exceed $10^5$.

输入的第一行包含一个整数 $t$（$1 \leq t \leq 10^4$）—— 表示测试用例的数量。

接下来是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $q$（$1 \leq n, q \leq 10^5$）—— 分别表示数组 $a$ 的长度以及查询的数量。

每个测试用例的第二行包含恰好 $n$ 个整数：$a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^9$）—— 表示数组 $a$ 的元素。

接下来的 $q$ 行每行包含一个查询，由两个整数 $type_j$ 和 $x_j$ 组成（$0 \leq type_j \leq 1$，$1 \leq x_j \leq 10^4$）。

保证在一个测试中，所有测试用例的 $n$ 值之和不超过 $10^5$；同理，所有测试用例的 $q$ 值之和也不超过 $10^5$。

For each test case, print $q$ numbers: the sum of the elements of the array $a$ after processing a query.

对于每个测试用例，输出 $q$ 个数字：每次处理完一个查询后数组 $a$ 中所有元素的和。

In the first test case, the array $a = [2]$ after the first query.

In the third test case, the array $a$ is modified as follows: $[1, 3, 2, 4, 10, 48]$ $\rightarrow$ $[7, 9, 2, 4, 10, 48]$ $\rightarrow$ $[7, 9, 7, 9, 15, 53]$ $\rightarrow$ $[7, 9, 7, 9, 15, 53]$ $\rightarrow$ $[10, 12, 10, 12, 18, 56]$ $\rightarrow$ $[22, 24, 22, 24, 30, 68]$ $\rightarrow$ $[23, 25, 23, 25, 31, 69]$.

在第一个测试用例中，第一次查询后数组 $a = [2]$。

在第三个测试用例中，数组 $a$ 按如下方式被修改：$[1, 3, 2, 4, 10, 48]$ $\rightarrow$ $[7, 9, 2, 4, 10, 48]$ $\rightarrow$ $[7, 9, 7, 9, 15, 53]$ $\rightarrow$ $[7, 9, 7, 9, 15, 53]$ $\rightarrow$ $[10, 12, 10, 12, 18, 56]$ $\rightarrow$ $[22, 24, 22, 24, 30, 68]$ $\rightarrow$ $[23, 25, 23, 25, 31, 69]$。