Tonya 在一张明信片上收到了一个长度为 $$$a$$$ 的数组作为生日礼物。由于某种原因,明信片原来是一个循环数组,因此严格位于第$$$n$$$右侧的元素的索引是$$$1$$$。 Tonya想更好地研究它,所以他买了一个机器人“Burenka-179”。
Burenka 的程序是一对数字 $$$(s, k)$$$,其中 $$$1 \leq s \leq n$$$, $$$1 \leq k \leq n-1$$$。请注意,$$$k$$$ 不能等于 $$$n$$$。最初,Tonya 将机器人放置在数组 $$$s$$$ 的位置。之后,Burenka 在数组中精确执行了 $$$n$$$ 步。如果在步骤开始时,Burenka 站在位置 $$$i$$$,则会发生以下情况:
1. 数字 $$$a_{i}$$$ 被添加到程序的有用性中。
2.“Burenka”将$$$k$$$位置向右移动(执行$$$i := i + k$$$,如果$$$i$$$变得大于$$$n$$$,则$$$i := i - n$$$)。
如果任何程序的初始有用性是 $$$0$$$,请帮助 Tonya 找到“Burenka”程序的最大可能有用性。
另外,Tony 的朋友 Ilyusha 要求他更改数组 $$$q$$$ 次。每次他想要为给定索引 $$$p$$$ 和值 $$$x$$$ 分配 $$$a_p := x$$$ 。您需要在每次更改后找到程序的最大可能有用性。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) 是测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$0 \le q \le 2 \cdot 10^5$$$)。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 数组的元素。
以下 $$$q$$$ 行包含更改,每行包含两个整数 $$$p$$$ 和 $$$x$$$ ($$$1 \leq p \leq n$$$, $$$1 \leq x \leq 10^9$$$),这意味着您应该分配 $$$a_p := x$$$。
保证所有测试用例的 $$$n$$$ 之和与 $$$q$$$ 之和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出 $$$q+1$$$ 数字——程序最初和每次更改后的最大有用性。
示例
输入 #1
4 2 1 1 2 1 3 4 4 4 1 3 2 2 6 4 6 1 1 3 11 9 3 1 7 9 4 5 2 3 6 8 3 1 2 1 9 1 6 3 1 1 1 1 1 1 1 5 4 4 3 8
输出 #1
3 5 14 16 24 24 24 57 54 36 36 6 18 27 28
注意
在第一个测试用例中,最初和每次请求之后,答案是在 $$$s = 1$$$、$$$k = 1$$$ 或 $$$s = 2$$$、$$$k = 1$$$ 处获得的。
在第二个测试用例中,最初,当 $$$s = 1$$$、$$$k = 2$$$ 或 $$$s = 3$$$、$$$k = 2$$$ 时获得答案。第一次请求后,在 $$$s = 2$$$、$$$k = 2$$$ 或 $$$s = 4$$$、$$$k = 2$$$ 处获得答案。