Тоне на день рождения подарили массив \(a\) длины \(n\), записанный на открытке. По какой-то причине открытка оказалась циклическим массивом, поэтому индекс элемента, находящегося строго справа от \(n\)-го, равен \(1\). Тоня захотел получше изучить её, поэтому он купил робота «Бурёнка-179».
Программа для «Бурёнки» задается парой чисел \((s, k)\), \(1 \leq s \leq n\), \(1 \leq k \leq n-1\). Обратите внимание, что \(k\) не может быть равно \(n\). Изначально Тоня ставит робота в позицию \(s\) массива. После этого «Бурёнка» сделает ровно \(n\) шагов по массиву. Если в начале очередного шага «Бурёнка» стоит в позиции \(i\), то происходит следующее:
- К полезности программы добавляется число \(a_{i}\).
- «Бурёнка» перемещается на \(k\) позиций вправо (выполняется \(i := i + k\), если \(i\) станет больше \(n\), то \(i := i - n\)).
Помогите Тоне найти максимальную возможную полезность программы для «Бурёнки», если изначальная полезность любой программы равна \(0\).
Кроме того, друг Тони Илюша \(q\) раз просит изменить массив. Каждое изменение состоит в присваивании \(a_p := x\) для некоторых чисел \(p\) и \(x\). Вам необходимо найти максимальную возможную полезность программы после каждого из таких изменений.
Выходные данные
Для каждого набора входных данных выведите \(q+1\) число — максимальную полезность программы изначально и после каждого запроса.
Примечание
В первом наборе входных данных изначально и после каждого запроса ответ достигается при \(s = 1\), \(k = 1\) или \(s = 2\), \(k = 1\).
Во втором наборе входных данных изначально ответ достигается при \(s = 1\), \(k = 2\) или \(s = 3\), \(k = 2\). После первого запроса ответ достигается при \(s = 2\), \(k = 2\) или \(s = 4\), \(k = 2\).
Примеры
| № | Входные данные | Выходные данные |
|
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
|
3
5
14
16
24
24
24
57
54
36
36
6
18
27
28
|