[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 𝑎1,𝑎2,…,𝑎𝑛$a_1,a_2,\dots ,a_n$. Process 𝑞$q$ queries of two types:

• query of the form "0 𝑥𝑗$x_j$": add the value 𝑥𝑗$x_j$ 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$.

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≤𝑡≤104$(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≤𝑛$1\le n$, 𝑞≤105$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: 𝑎1,𝑎2,…,𝑎𝑛$a_1,a_2,\dots ,a_n$ (1≤𝑎𝑖≤109$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$ (0≤𝑡𝑦𝑝𝑒𝑗≤1$(0\le typ{e}_j\le 1$, 1≤𝑥𝑗≤104$1\le x_j\le {10}^4$).

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

It is guaranteed that the sum of values 𝑛$n$ over all test cases in a test does not exceed 105${10}^5$. Similarly, the sum of values 𝑞$q$ over all test cases does not exceed 105${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 𝑎=[2]$a=[2]$ after the first query.

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