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

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