说明

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

• query of the form "$0$ $x_{j}$": add the $x_{j}$ value 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$.

输入格式

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$ nd the number of queries.

The second line of each test case contains exactly $n$ integers:$a_{1}$,$a_{2}$,…,$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 valuesqqover all test cases does not exceed $10^5$

输出格式

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

样例

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