You are given n of integers a1,a2,…,an. Process q queries of two types:

(资料图片仅供参考)

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

Note that when processing the query, we look specifically at the odd/even value of ai, 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++).

Input

The first line of the input contains an integer t (1≤t≤104) — 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≤n, q≤105) — the length of array a and the number of queries.

The second line of each test case contains exactly n integers: a1,a2,…,an (1≤ai≤109) — elements of the array a.

The following q lines contain queries as two integers typej and xj (0≤typej≤1, 1≤xj≤104).

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

Output

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

----------------------------------------

给定 n 个整数 a1,a2,…,an。 处理两种类型的 q 查询：

“0 xj”形式的查询：将值 xj 添加到数组 a 的所有偶数元素，“1 xj”形式的查询：将值 xj 添加到数组 a 的所有奇数元素。

请注意，在处理查询时，我们专门查看 ai 的奇/偶值，而不是其索引。

处理完每个查询后，打印数组 a 的元素之和。

请注意，某些测试用例的答案不适合 32 位整数类型，因此您应该在编程语言中至少使用 64 位整数类型（例如 C++ 的 long long）。

输入

输入的第一行包含一个整数 t (1≤t≤104) — 测试用例的数量。

测试用例的描述如下。

每个测试用例的第一行包含两个整数n和q（1≤n，q≤105）——数组a的长度和查询的数量。

每个测试用例的第二行恰好包含 n 个整数：a1,a2,…,an (1≤ai≤109) — 数组 a 的元素。

以下 q 行包含两个整数 typej 和 xj (0≤typej≤1, 1≤xj≤104) 的查询。

保证一次测试中所有测试用例的 n 值之和不超过 105。同样，所有测试用例的 q 值之和不超过 105。

输出

对于每个测试用例，打印 q 个数字：处理查询后数组 a 的元素之和。

-------------------------------------

代码明明没问题的，结果报错了好几次。。。