给你 $$$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$$$ 的元素之和。
示例
输入 #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
输出 #1
2 11 14 29 80 100 100 100 118 190 196 3000000094 3000060094 3000060400 3000060952 3000061270 3000061366 3000061366
注意
在第一个测试用例中,第一个查询之后的数组 $$$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]$$$。