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:   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.
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$$$.
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.
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def prime_factorize(n):
    ans = []
    for i in range(2, int(n ** (1 / 2)) + 1):
        while True:
            if n % i:
                break
            ans.append(i)
            n //= i
        if n == 1:
            break
    if not n == 1:
        ans.append(n)
    return ans
t = int(input())
ans = []
pow2 = [1]
for _ in range(25):
    pow2.append(2 * pow2[-1])
for _ in range(t):
    (n, q) = map(int, input().split())
    a = list(map(float, input().split()))
    p = list(set(prime_factorize(n)))
    d = [n // i for i in p]
    d.sort()
    l = len(d)
    (y, z) = ([], [0])
    for u in d:
        z.append(u + z[-1])
        for i in range(u):
            s = 0
            for j in range(i, n, u):
                s += a[j]
            s *= u
            y.append(s)
    m = len(y).bit_length()
    pm = pow2[m]
    ma = [0.0] * (2 * pm)
    for i in range(len(y)):
        ma[i + pm] = y[i]
    for i in range(pm - 1, 0, -1):
        ma[i] = max(ma[2 * i], ma[2 * i + 1])
    ans0 = int(ma[1])
    ans.append(ans0)
    for _ in range(q):
        (p, x) = map(int, input().split())
        p -= 1
        if x == a[p]:
            ans0 = int(ma[1])
            ans.append(ans0)
            continue
        c = x - a[p]
        a[p] = x + 0.0
        for i in range(l):
            j = z[i] + p % d[i]
            y[j] += d[i] * c
            ma[j + pm] = y[j]
            j = (j + pm) // 2
            while j:
                ma[j] = max(ma[2 * j], ma[2 * j + 1])
                j //= 2
        ans0 = int(ma[1])
        ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def prime_factorize(n):
    ans = []
    for i in range(2, int(n ** (1 / 2)) + 1):
        while True:
            if n % i:
                break
            ans.append(i)
            n //= i
        if n == 1:
            break
    if not n == 1:
        ans.append(n)
    return ans
t = int(input())
ans = []
pow2 = [1]
for _ in range(25):
    pow2.append(2 * pow2[-1])
for _ in range(t):
    (n, q) = map(int, input().split())
    a = list(map(int, input().split()))
    p = list(set(prime_factorize(n)))
    d = [n // i for i in p]
    d.sort()
    l = len(d)
    (y, z) = ([], [0])
    for u in d:
        z.append(u + z[-1])
        for i in range(u):
            s = 0
            for j in range(i, n, u):
                s += a[j]
            s *= u
            y.append(s)
    m = len(y).bit_length()
    pm = pow2[m]
    ma = [0] * (2 * pm)
    for i in range(len(y)):
        ma[i + pm] = y[i]
    for i in range(pm - 1, 0, -1):
        ma[i] = max(ma[2 * i], ma[2 * i + 1])
    ans0 = ma[1]
    ans.append(ans0)
    for _ in range(q):
        (p, x) = map(int, input().split())
        p -= 1
        if x == a[p]:
            ans0 = ma[1]
            ans.append(ans0)
            continue
        c = x - a[p]
        a[p] = x
        for i in range(l):
            j = z[i] + p % d[i]
            y[j] += d[i] * c
            ma[j + pm] = y[j]
            j = (j + pm) // 2
            while j and ma[j] ^ max(ma[2 * j], ma[2 * j + 1]):
                ma[j] = max(ma[2 * j], ma[2 * j + 1])
                j //= 2
        ans0 = ma[1]
        ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))
class SegmentTree:

    def __init__(self, data, default=0, func=max):
        """"""
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()
        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])

    def __delitem__(self, idx):
        self[idx] = self._default

    def __getitem__(self, idx):
        return self.data[idx + self._size]

    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1

    def __len__(self):
        return self._len

    def query(self, start, stop):
        """"""
        start += self._size
        stop += self._size
        res_left = res_right = self._default
        while start < stop:
            if start & 1:
                res_left = self._func(res_left, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res_right = self._func(self.data[stop], res_right)
            start >>= 1
            stop >>= 1
        return self._func(res_left, res_right)

    def __repr__(self):
        return 'SegmentTree({0})'.format(self.data)
import sys, random
input = sys.stdin.readline
out = []
t = int(input())
for _ in range(t):
    (n, q) = map(int, input().split())
    a = list(map(int, input().split()))
    pr = []
    m = n
    for i in range(2, 10 ** 3):
        if m % i == 0:
            pr.append(i)
            while m % i == 0:
                m //= i
    if m > 1:
        pr.append(m)
    sz = len(pr)
    ''
    segs = []
    vals = []
    for p in pr:
        m = n // p
        l = [0] * m
        for i in range(n):
            l[i % m] += a[i]
        segs.append(SegmentTree(l))
        vals.append(n // p * segs[-1].data[1])
    out.append(max(vals))
    for _ in range(q):
        (p, x) = map(int, input().split())
        p -= 1
        diff = x - a[p]
        a[p] = x
        for i in range(sz):
            pp = pr[i]
            m = n // pp
            segs[i][p % m] += diff
            vals[i] = n // pp * segs[i].data[1]
        out.append(max(vals))
print('\n'.join(map(str, out)))