codeforces#P1718C. Tonya and Burenka-179
Tonya and Burenka-179
Description
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:
- The number $a_{i}$ is added to the usefulness of the program.
- "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.
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.
Samples
<div class="test-example-line test-example-line-even test-example-line-0">4</div><div class="test-example-line test-example-line-odd test-example-line-1">2 1</div><div class="test-example-line test-example-line-odd test-example-line-1">1 2</div><div class="test-example-line test-example-line-odd test-example-line-1">1 3</div><div class="test-example-line test-example-line-even test-example-line-2">4 4</div><div class="test-example-line test-example-line-even test-example-line-2">4 1 3 2</div><div class="test-example-line test-example-line-even test-example-line-2">2 6</div><div class="test-example-line test-example-line-even test-example-line-2">4 6</div><div class="test-example-line test-example-line-even test-example-line-2">1 1</div><div class="test-example-line test-example-line-even test-example-line-2">3 11</div><div class="test-example-line test-example-line-odd test-example-line-3">9 3</div><div class="test-example-line test-example-line-odd test-example-line-3">1 7 9 4 5 2 3 6 8</div><div class="test-example-line test-example-line-odd test-example-line-3">3 1</div><div class="test-example-line test-example-line-odd test-example-line-3">2 1</div><div class="test-example-line test-example-line-odd test-example-line-3">9 1</div><div class="test-example-line test-example-line-even test-example-line-4">6 3</div><div class="test-example-line test-example-line-even test-example-line-4">1 1 1 1 1 1</div><div class="test-example-line test-example-line-even test-example-line-4">1 5</div><div class="test-example-line test-example-line-even test-example-line-4">4 4</div><div class="test-example-line test-example-line-even test-example-line-4">3 8</div><div class="test-example-line test-example-line-even test-example-line-4"></div>
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$.