### 问题描述 小蓝和小桥在玩一个有趣的游戏。他们有一个长度为 $n$ 的数组 $a$，并且需要处理 $q$ 次操作，操作分为两种： - 类型为 $0$，表示将所有偶数元素加上 $x_j$。 - 类型为 $1$，表示将所有奇数元素加上 $x_j$。 每次操作后，他们需要计算数组 $a$ 中所有元素的和。小蓝和小桥想知道，在他们的操作后，数组 $a$ 的总和会是多少呢？ 他们决定通过协作完成这个任务，小蓝处理所有偶数元素，小桥处理所有奇数元素。 ### 输入格式 第一行包含一个整数 $t$，表示测试数据组数。 对于每组数据，第一行包含两个整数 $n$ 和 $q$，表示数组 $a$ 的长度和操作次数。 第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示数组 $a$ 中的元素。 接下来 $q$ 行，每行包含两个整数 $type_j$ 和 $x_j$，表示一次操作。其中 $type_j$ 表示操作类型，$0$ 表示将所有偶数元素加上 $x_j$，$1$ 表示将所有奇数元素加上 $x_j$。 ### 输出格式 对于每组数据，输出 $q$ 行，每行一个整数，表示每次操作后，数组 $a$ 中所有元素的和。 ### 样例输入 ```txt 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 ``` ### 样例输出 ```txt 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]$。 ### 评测数据规模 对于 $100$% 的评测数据，$1\leq t\leq 5,1 \leq n,q \leq 10^5,1 \leq a_i \leq 10^9,0 \leq type_j \leq 1,1 \leq x_j \leq 10^4$。