A15329 | Tonya and Burenka-179

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.

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$ .

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