## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [Solution] Even-Odd Increments Codeforces Solution

B. Even-Odd Increments
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given $n$ of integers ${a}_{1},{a}_{2},\dots ,{a}_{n}$. Process $q$ queries of two types:

• query of the form "${x}_{j}$": add the value ${x}_{j}$ to all even elements of the array $a$,
• query of the form "${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$.

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$ $\left(1\le t\le {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\le n$$q\le {10}^{5}$) — the length of array $a$ and the number of queries.

The second line of each test case contains exactly $n$ integers: ${a}_{1},{a}_{2},\dots ,{a}_{n}$ ($1\le {a}_{i}\le {10}^{9}$) — elements of the array $a$.

The following $q$ lines contain queries as two integers $typ{e}_{j}$ and ${x}_{j}$ $\left(0\le typ{e}_{j}\le 1$$1\le {x}_{j}\le {10}^{4}$).

Solution Click Below:-  👉
👇👇👇👇👇

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 values $q$ over all test cases does not exceed ${10}^{5}$.

Output

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

Note

In the first test case, the array $a=\left[2\right]$ after the first query.

In the third test case, the array $a$ is modified as follows: $\left[1,3,2,4,10,48\right]$ $\to$ $\left[7,9,2,4,10,48\right]$ $\to$ $\left[7,9,7,9,15,53\right]$ $\to$ $\left[7,9,7,9,15,53\right]$ $\to$ $\left[10,12,10,12,18,56\right]$ $\to$ $\left[22,24,22,24,30,68\right]$ $\to$ $\left[23,25,23,25,31,69\right]$.