C. Тоня и Бурёнка-179
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Тоне на день рождения подарили массив $$$a$$$ длины $$$n$$$, записанный на открытке. По какой-то причине открытка оказалась циклическим массивом, поэтому индекс элемента, находящегося строго справа от $$$n$$$-го, равен $$$1$$$. Тоня захотел получше изучить её, поэтому он купил робота «Бурёнка-179».

Программа для «Бурёнки» задается парой чисел $$$(s, k)$$$, $$$1 \leq s \leq n$$$, $$$1 \leq k \leq n-1$$$. Обратите внимание, что $$$k$$$ не может быть равно $$$n$$$. Изначально Тоня ставит робота в позицию $$$s$$$ массива. После этого «Бурёнка» сделает ровно $$$n$$$ шагов по массиву. Если в начале очередного шага «Бурёнка» стоит в позиции $$$i$$$, то происходит следующее:

  1. К полезности программы добавляется число $$$a_{i}$$$.
  2. «Бурёнка» перемещается на $$$k$$$ позиций вправо (выполняется $$$i := i + k$$$, если $$$i$$$ станет больше $$$n$$$, то $$$i := i - n$$$).

Помогите Тоне найти максимальную возможную полезность программы для «Бурёнки», если изначальная полезность любой программы равна $$$0$$$.

Кроме того, друг Тони Илюша $$$q$$$ раз просит изменить массив. Каждое изменение состоит в присваивании $$$a_p := x$$$ для некоторых чисел $$$p$$$ и $$$x$$$. Вам необходимо найти максимальную возможную полезность программы после каждого из таких изменений.

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

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

В первой строке каждого набора входных данных содержится два целых числа $$$n$$$ и $$$q$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$0 \le q \le 2 \cdot 10^5$$$).

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

В следующих $$$q$$$ строках находятся описания изменений, каждое из которых состоит из двух целых чисел $$$p$$$ и $$$x$$$ ($$$1 \leq p \leq n$$$, $$$1 \leq x \leq 10^9$$$), означающих, что необходимо выполнить $$$a_p := x$$$.

Гарантируется, что сумма $$$n$$$ и сумма $$$q$$$ по всем тестам не превосходят $$$2 \cdot 10^5$$$.

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

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

Пример
Входные данные
4
2 1
1 2
1 3
4 4
4 1 3 2
2 6
4 6
1 1
3 11
9 3
1 7 9 4 5 2 3 6 8
3 1
2 1
9 1
6 3
1 1 1 1 1 1
1 5
4 4
3 8
Выходные данные
3
5
14
16
24
24
24
57
54
36
36
6
18
27
28
Примечание

В первом наборе входных данных изначально и после каждого запроса ответ достигается при $$$s = 1$$$, $$$k = 1$$$ или $$$s = 2$$$, $$$k = 1$$$.

Во втором наборе входных данных изначально ответ достигается при $$$s = 1$$$, $$$k = 2$$$ или $$$s = 3$$$, $$$k = 2$$$. После первого запроса ответ достигается при $$$s = 2$$$, $$$k = 2$$$ или $$$s = 4$$$, $$$k = 2$$$.