B. Чётно-нечётные прибавления
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$. Обработайте $$$q$$$ запросов двух типов:

  • запрос вида «0 $$$x_j$$$» — ко всем чётным элементам массива $$$a$$$ прибавить число $$$x_j$$$,
  • запрос вида «1 $$$x_j$$$» — ко всем нечётным элементам массива $$$a$$$ прибавить число $$$x_j$$$.

Обратите внимание, что при обработке запроса мы смотрим именно на чётность/нечётность значения $$$a_i$$$, а не на его индекс.

После обработки каждого запроса выведите сумму элементов массива $$$a$$$.

Обратите внимание, что для некоторых наборов входных данных ответ не будет помещаться в 32-х битных целочисленный тип, вы должны использовать 64-битный целочисленный тип вашего языка (например, long long в C++).

Входные данные

В первой строке входных данных задано целое число $$$t$$$ $$$(1 \leq t \leq 10^4$$$) — количество наборов входных данных.

Далее следуют описания наборов входных данных.

В первой строке каждого набора входных данных содержится два целых числа $$$n$$$ и $$$q$$$ ($$$1 \leq n$$$, $$$q \leq 10^5$$$) — длина массива $$$a$$$ и количество запросов.

Во второй строке каждого набора входных данных содержится ровно $$$n$$$ целых чисел: $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — элементы массива $$$a$$$.

В следующих $$$q$$$ строках содержатся запросы в виде двух целых чисел $$$type_j$$$ и $$$x_j$$$ $$$(0 \leq type_j \leq 1$$$, $$$1 \leq x_j \leq 10^4$$$).

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$. Аналогично, сумма значений $$$q$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

Выходные данные

Для каждого набора входных данных выведите $$$q$$$ чисел — сумму элементов массива $$$a$$$ после обработки каждого запроса.

Пример
Входные данные
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
Примечание

В первом наборе входных данных массив $$$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]$$$.