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 os
import sys
from io import BytesIO, IOBase
from collections import Counter
from heapq import heappush, heappop

def main():
    MAX_N = 2 * 10 ** 5
    prime_factor = list(range(MAX_N + 1))
    for i in range(2, int((MAX_N + 1) ** 0.5) + 1):
        if prime_factor[i] != i:
            continue
        for j in range(i * i, MAX_N + 1, i):
            prime_factor[j] = i

    def prime_factors(x):
        ret = set()
        while x != 1:
            ret.add(prime_factor[x])
            x //= prime_factor[x]
        return ret
    t = int(input())
    for _ in range(t):
        (n, q) = map(int, input().split())
        a = [int(ai) for ai in input().split()]
        factors = prime_factors(n)
        (d, heap) = ([[] for _ in range(n + 1)], [])
        for factor in factors:
            step = n // factor
            for start in range(step):
                d[factor].append(sum(a[start::step]) * step)
                heappush(heap, -d[factor][-1])
        print(-heap[0])
        removed = Counter()
        for _ in range(q):
            (p, x) = map(int, input().split())
            p -= 1
            for factor in factors:
                step = n // factor
                removed[d[factor][p % step]] += 1
                d[factor][p % step] += (x - a[p]) * step
                heappush(heap, -d[factor][p % step])
            a[p] = x
            while removed[-heap[0]]:
                removed[-heappop(heap)] -= 1
            print(-heap[0])
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
if __name__ == '__main__':
    main()
class SegmentTree:

    def __init__(self, n, oper=max, e=0):
        self.n = n
        self.oper = oper
        self.e = e
        self.log = (n - 1).bit_length()
        self.size = 1 << self.log
        self.data = [e] * (2 * self.size)

    def update(self, k):
        self.data[k] = self.oper(self.data[2 * k], self.data[2 * k + 1])

    def build(self, arr):
        for i in range(self.n):
            self.data[self.size + i] = arr[i]
        for i in range(self.size - 1, 0, -1):
            self.update(i)

    def set(self, p, x):
        p += self.size
        self.data[p] = x
        for i in range(self.log):
            p >>= 1
            self.update(p)

    def get(self, p):
        return self.data[p + self.size]

    def prod(self, l, r):
        sml = smr = self.e
        l += self.size
        r += self.size
        while l < r:
            if l & 1:
                sml = self.oper(sml, self.data[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self.oper(self.data[r], smr)
            l >>= 1
            r >>= 1
        return self.oper(sml, smr)

    def all_prod(self):
        return self.data[1]

def solve():
    (n, q) = map(int, input().split())
    arr = list(map(int, input().split()))
    div = []
    n1 = n
    d = 2
    while d * d <= n1:
        if n1 % d == 0:
            div.append(n // d)
        while n1 % d == 0:
            n1 //= d
        d += 1
    if n1 != 1 and n1 != n:
        div.append(n // n1)
    seg = []
    for d in div:
        L = [0] * d
        for (i, a) in enumerate(arr):
            L[i % d] += a * d
        s = SegmentTree(d)
        s.build(L)
        seg.append(s)
    su = sum(arr)
    res = su
    for s in seg:
        res = max(res, s.all_prod())
    ans = [res]
    for t in range(q):
        (i, x) = map(int, input().split())
        i -= 1
        (x, arr[i]) = (x - arr[i], x)
        su += x
        res = su
        for s in seg:
            s.set(i % s.n, s.get(i % s.n) + x * s.n)
            res = max(res, s.all_prod())
        ans.append(res)
    print('\n'.join((str(a) for a in ans)))
t = int(input())
for i in range(t):
    solve()
from collections import defaultdict, Counter, deque
from math import sqrt, log10, log, floor, factorial, gcd, ceil, log2
from bisect import bisect_left, bisect_right, insort
from itertools import permutations, combinations
import sys, io, os
input = sys.stdin.readline
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
inf = float('inf')
mod = 10 ** 9 + 7

def yn(a):
    print('YES' if a else 'NO')
cl = lambda a, b: (a + b - 1) // b

class SortedList:

    def __init__(self, iterable=[], _load=200):
        """"""
        values = sorted(iterable)
        self._len = _len = len(values)
        self._load = _load
        self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
        self._list_lens = [len(_list) for _list in _lists]
        self._mins = [_list[0] for _list in _lists]
        self._fen_tree = []
        self._rebuild = True

    def _fen_build(self):
        """"""
        self._fen_tree[:] = self._list_lens
        _fen_tree = self._fen_tree
        for i in range(len(_fen_tree)):
            if i | i + 1 < len(_fen_tree):
                _fen_tree[i | i + 1] += _fen_tree[i]
        self._rebuild = False

    def _fen_update(self, index, value):
        """"""
        if not self._rebuild:
            _fen_tree = self._fen_tree
            while index < len(_fen_tree):
                _fen_tree[index] += value
                index |= index + 1

    def _fen_query(self, end):
        """"""
        if self._rebuild:
            self._fen_build()
        _fen_tree = self._fen_tree
        x = 0
        while end:
            x += _fen_tree[end - 1]
            end &= end - 1
        return x

    def _fen_findkth(self, k):
        """"""
        _list_lens = self._list_lens
        if k < _list_lens[0]:
            return (0, k)
        if k >= self._len - _list_lens[-1]:
            return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
        if self._rebuild:
            self._fen_build()
        _fen_tree = self._fen_tree
        idx = -1
        for d in reversed(range(len(_fen_tree).bit_length())):
            right_idx = idx + (1 << d)
            if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
                idx = right_idx
                k -= _fen_tree[idx]
        return (idx + 1, k)

    def _delete(self, pos, idx):
        """"""
        _lists = self._lists
        _mins = self._mins
        _list_lens = self._list_lens
        self._len -= 1
        self._fen_update(pos, -1)
        del _lists[pos][idx]
        _list_lens[pos] -= 1
        if _list_lens[pos]:
            _mins[pos] = _lists[pos][0]
        else:
            del _lists[pos]
            del _list_lens[pos]
            del _mins[pos]
            self._rebuild = True

    def _loc_left(self, value):
        """"""
        if not self._len:
            return (0, 0)
        _lists = self._lists
        _mins = self._mins
        (lo, pos) = (-1, len(_lists) - 1)
        while lo + 1 < pos:
            mi = lo + pos >> 1
            if value <= _mins[mi]:
                pos = mi
            else:
                lo = mi
        if pos and value <= _lists[pos - 1][-1]:
            pos -= 1
        _list = _lists[pos]
        (lo, idx) = (-1, len(_list))
        while lo + 1 < idx:
            mi = lo + idx >> 1
            if value <= _list[mi]:
                idx = mi
            else:
                lo = mi
        return (pos, idx)

    def _loc_right(self, value):
        """"""
        if not self._len:
            return (0, 0)
        _lists = self._lists
        _mins = self._mins
        (pos, hi) = (0, len(_lists))
        while pos + 1 < hi:
            mi = pos + hi >> 1
            if value < _mins[mi]:
                hi = mi
            else:
                pos = mi
        _list = _lists[pos]
        (lo, idx) = (-1, len(_list))
        while lo + 1 < idx:
            mi = lo + idx >> 1
            if value < _list[mi]:
                idx = mi
            else:
                lo = mi
        return (pos, idx)

    def add(self, value):
        """"""
        _load = self._load
        _lists = self._lists
        _mins = self._mins
        _list_lens = self._list_lens
        self._len += 1
        if _lists:
            (pos, idx) = self._loc_right(value)
            self._fen_update(pos, 1)
            _list = _lists[pos]
            _list.insert(idx, value)
            _list_lens[pos] += 1
            _mins[pos] = _list[0]
            if _load + _load < len(_list):
                _lists.insert(pos + 1, _list[_load:])
                _list_lens.insert(pos + 1, len(_list) - _load)
                _mins.insert(pos + 1, _list[_load])
                _list_lens[pos] = _load
                del _list[_load:]
                self._rebuild = True
        else:
            _lists.append([value])
            _mins.append(value)
            _list_lens.append(1)
            self._rebuild = True

    def discard(self, value):
        """"""
        _lists = self._lists
        if _lists:
            (pos, idx) = self._loc_right(value)
            if idx and _lists[pos][idx - 1] == value:
                self._delete(pos, idx - 1)

    def remove(self, value):
        """"""
        _len = self._len
        self.discard(value)
        if _len == self._len:
            raise ValueError('{0!r} not in list'.format(value))

    def pop(self, index=-1):
        """"""
        (pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
        value = self._lists[pos][idx]
        self._delete(pos, idx)
        return value

    def bisect_left(self, value):
        """"""
        (pos, idx) = self._loc_left(value)
        return self._fen_query(pos) + idx

    def bisect_right(self, value):
        """"""
        (pos, idx) = self._loc_right(value)
        return self._fen_query(pos) + idx

    def count(self, value):
        """"""
        return self.bisect_right(value) - self.bisect_left(value)

    def __len__(self):
        """"""
        return self._len

    def __getitem__(self, index):
        """"""
        (pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
        return self._lists[pos][idx]

    def __delitem__(self, index):
        """"""
        (pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
        self._delete(pos, idx)

    def __contains__(self, value):
        """"""
        _lists = self._lists
        if _lists:
            (pos, idx) = self._loc_left(value)
            return idx < len(_lists[pos]) and _lists[pos][idx] == value
        return False

    def __iter__(self):
        """"""
        return (value for _list in self._lists for value in _list)

    def __reversed__(self):
        """"""
        return (value for _list in reversed(self._lists) for value in reversed(_list))

    def __repr__(self):
        """"""
        return 'SortedList({0})'.format(list(self))
from functools import lru_cache
import math as mt
MAXN = 2 * 10 ** 5 + 100
spf = [i for i in range(MAXN)]

def sieve():
    for i in range(4, MAXN, 2):
        spf[i] = 2
    for i in range(3, mt.ceil(mt.sqrt(MAXN))):
        if spf[i] == i:
            for j in range(i * i, MAXN, i):
                if spf[j] == j:
                    spf[j] = i

@lru_cache(None)
def getFactorization(x):
    ret = set()
    while x != 1:
        ret.add(spf[x])
        x = x // spf[x]
    return ret
sieve()
t = int(input())
for i in range(t):
    (n, q) = [int(i) for i in input().split()]
    l = [int(i) for i in input().split()]
    fac = getFactorization(n)
    d = [[] for i in range(n + 1)]
    s = SortedList()
    for numbers_taken in fac:
        step = n // numbers_taken
        for start in range(step):
            counter = 0
            for k in range(start, n, step):
                counter += l[k] * step
            d[numbers_taken].append(counter)
            s.add(counter)
    print(s[-1])
    for i in range(q):
        (p, x) = [int(i) for i in input().split()]
        p -= 1
        old = l[p]
        l[p] = x
        diff = x - old
        for numbers_taken in fac:
            step = n // numbers_taken
            index_in_dict = p % step
            old_value_in_dict = d[numbers_taken][index_in_dict]
            new_value_in_dict = old_value_in_dict + diff * step
            d[numbers_taken][index_in_dict] = new_value_in_dict
            s.remove(old_value_in_dict)
            s.add(new_value_in_dict)
        print(s[-1])
''