题目描述

给定 $n$ 个整数 $a_1, a_2, \ldots, a_n$。你需要处理 $q$ 个两种类型的操作：

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

注意，在处理操作时，是根据 $a_i$ 的奇偶性（而不是下标的奇偶性）来判断。

每次操作后，输出数组 $a$ 所有元素的和。

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

输入格式

输入的第一行包含一个整数 $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$。

输出格式

对于每个测试用例，输出 $q$ 个数字，分别表示每次操作后数组 $a$ 所有元素的和。

说明/提示

在第一个测试用例中，数组 $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]$。

由 ChatGPT 4.1 翻译

样例

4
1 1
1
1 1
3 3
1 2 4
0 2
1 3
0 5
6 7
1 3 2 4 10 48
1 6
0 5
0 4
0 5
1 3
0 12
0 1
6 7
1000000000 1000000000 1000000000 11 15 17
0 17
1 10000
1 51
0 92
0 53
1 16
0 1

2
11
14
29
80
100
100
100
118
190
196
3000000094
3000060094
3000060400
3000060952
3000061270
3000061366
3000061366