C. Tonya and Burenka-179
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Tonya was given an array of $$$a$$$ of length $$$n$$$ written on a postcard for his birthday. For some reason, the postcard turned out to be a cyclic array, so the index of the element located strictly to the right of the $$$n$$$-th is $$$1$$$. Tonya wanted to study it better, so he bought a robot "Burenka-179".

A program for Burenka is a pair of numbers $$$(s, k)$$$, where $$$1 \leq s \leq n$$$, $$$1 \leq k \leq n-1$$$. Note that $$$k$$$ cannot be equal to $$$n$$$. Initially, Tonya puts the robot in the position of the array $$$s$$$. After that, Burenka makes exactly $$$n$$$ steps through the array. If at the beginning of a step Burenka stands in the position $$$i$$$, then the following happens:

  1. The number $$$a_{i}$$$ is added to the usefulness of the program.
  2. "Burenka" moves $$$k$$$ positions to the right ($$$i := i + k$$$ is executed, if $$$i$$$ becomes greater than $$$n$$$, then $$$i := i - n$$$).

Help Tonya find the maximum possible usefulness of a program for "Burenka" if the initial usefulness of any program is $$$0$$$.

Also, Tony's friend Ilyusha asks him to change the array $$$q$$$ times. Each time he wants to assign $$$a_p := x$$$ for a given index $$$p$$$ and a value $$$x$$$. You need to find the maximum possible usefulness of the program after each of these changes.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) is the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$q$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$0 \le q \le 2 \cdot 10^5$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — elements of the array.

The following $$$q$$$ lines contain changes, each of them contains two integers $$$p$$$ and $$$x$$$ ($$$1 \leq p \leq n$$$, $$$1 \leq x \leq 10^9$$$), meaning you should assign $$$a_p := x$$$.

It is guaranteed that the sum of $$$n$$$ and the sum of $$$q$$$ over all test cases do not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output $$$q+1$$$ numbers — the maximum usefulness of a program initially and after each of the changes.

Example
Input
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
Output
3
5
14
16
24
24
24
57
54
36
36
6
18
27
28
Note

In the first test case, initially and after each request, the answer is achieved at $$$s = 1$$$, $$$k = 1$$$ or $$$s = 2$$$, $$$k = 1$$$.

In the second test case, initially, the answer is achieved when $$$s = 1$$$, $$$k = 2$$$ or $$$s = 3$$$, $$$k = 2$$$. After the first request, the answer is achieved at $$$s = 2$$$, $$$k = 2$$$ or $$$s = 4$$$, $$$k = 2$$$.