Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

B. 250 тысяч тонн тротила
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Лёша участвует в съёмке очередного ролика BrMeast, и BrMeast попросил Лёшу подготовить 250 тысяч тонн тротила, но Лёша его не расслышал, поэтому он подготовил $$$n$$$ коробок. Лёша хочет погрузить эти коробки в грузовики, для этого он расставил их в ряд, $$$i$$$-я слева коробка имеет вес $$$a_i$$$ тонн.

Все грузовики, которые собирается использовать Лёша, вмещают в себя одинаковое количество коробок, обозначим это количество $$$k$$$. Тогда погрузка происходит следующим образом:

  • В первый грузовик помещаются первые $$$k$$$ коробок,
  • Во второй грузовик помещаются вторые $$$k$$$ коробок,
  • $$$\dotsb$$$
  • В $$$\frac{n}{k}$$$-й грузовик помещаются последние $$$k$$$ коробок.

По окончании погрузки в каждом грузовике должно быть ровно $$$k$$$ коробок. То есть, если в какой-то момент в грузовик не получится загрузить ровно $$$k$$$ коробок, то вариант погрузки с таким $$$k$$$ невозможен.

Лёша ненавидит справедливость, так что он хочет, чтобы максимальная абсолютная разница между суммарным весом каких-либо двух грузовиков была как можно больше. Если грузовик один, эта величина равна $$$0$$$.

У Лёши есть достаточно много связей, поэтому для каждого $$$1 \leq k \leq n$$$ он может найти такую компанию, что каждый её грузовик вмещает в себя ровно $$$k$$$ коробок. Выведите максимальную абсолютную разницу между суммарным весом каких-либо двух грузовиков.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \leq n \leq 150\,000$$$) — количество коробок.

Во второй строке даны $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — веса коробок.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$150\,000$$$.

Выходные данные

Для каждого набора данных выведите одно число — ответ на задачу.

Пример
Входные данные
5
2
1 2
6
10 2 3 6 1 3
4
1000000000 1000000000 1000000000 1000000000
15
60978 82265 78961 56708 39846 31071 4913 4769 29092 91348 64119 72421 98405 222 14294
8
19957 69913 37531 96991 57838 21008 14207 19198
Выходные данные
1
9
0
189114
112141
Примечание

В первом случае выгодно взять два грузовика, в первом будет только первая коробка, во втором только вторая.

Во втором случае выгодно взять шесть грузовиков, в каждом по одной коробке. Тогда максимум равен $$$10$$$, минимум равен $$$1$$$, ответ равен $$$10 - 1 = 9$$$.

В третьем случае при любом возможном $$$k$$$ в грузовиках будет одинаковый суммарный вес коробок, то есть ответ равен $$$0$$$.