B. Переместите в конец
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a$$$, состоящий из $$$n$$$ целых чисел.

Для каждого целого числа $$$k$$$ от $$$1$$$ до $$$n$$$ вам необходимо выполнить следующее:

  1. выбрать произвольный элемент массива $$$a$$$ и переместить его в правый конец массива (вы можете выбрать последний элемент, тогда массив не изменится);
  2. вывести сумму $$$k$$$ последних элементов массива $$$a$$$;
  3. переместить элемент, который вы выбрали на первом шаге, на его исходную позицию (восстановить исходный массив $$$a$$$).

Для каждого $$$k$$$ вы выбираете элемент, который перемещаете, таким образом, чтобы значение, которое вы выводите, было максимально возможным.

Вычислите значение, которое вы выведете для каждого $$$k$$$.

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

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

Каждый набор входных данных состоит из двух строк:

  • первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$);
  • вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

Дополнительное ограничение на входные данные: сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите $$$n$$$ целых чисел. $$$i$$$-е из этих чисел должно быть равно максимальному значению, которое вы можете вывести, если $$$k=i$$$.

Пример
Входные данные
4
7
13 5 10 14 8 15 13
6
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
1
42
2
7 5
Выходные данные
15 28 42 50 63 73 78 
1000000000 2000000000 3000000000 4000000000 5000000000 6000000000 
42 
7 12
Примечание

Рассмотрим первый набор входных данных из условия:

  • когда $$$k = 1$$$, вы можете переместить $$$6$$$-й элемент в конец, массив становится $$$[13, 5, 10, 14, 8, 13, 15]$$$, и значение, которое вы выводите, равно $$$15$$$;
  • когда $$$k = 2$$$, вы можете переместить $$$6$$$-й элемент в конец, массив становится $$$[13, 5, 10, 14, 8, 13, 15]$$$, и значение, которое вы выводите, равно $$$13 + 15 = 28$$$;
  • когда $$$k = 3$$$, вы можете переместить $$$4$$$-й элемент в конец, массив становится $$$[13, 5, 10, 8, 15, 13, 14]$$$, и значение, которое вы выводите, равно $$$15 + 13 + 14 = 42$$$;
  • когда $$$k = 4$$$, вы можете переместить $$$5$$$-й элемент в конец, массив становится $$$[13, 5, 10, 14, 15, 13, 8]$$$, и значение, которое вы выводите, равно $$$14 + 15 + 13 + 8 = 50$$$;
  • когда $$$k = 5$$$, вы можете переместить $$$1$$$-й элемент в конец, массив становится $$$[5, 10, 14, 8, 15, 13, 13]$$$, и значение, которое вы выводите, равно $$$14 + 8 + 15 + 13 + 13 = 63$$$;
  • когда $$$k = 6$$$, вы можете переместить $$$1$$$-й элемент в конец, массив становится $$$[5, 10, 14, 8, 15, 13, 13]$$$, и значение, которое вы выводите, равно $$$10 + 14 + 8 + 15 + 13 + 13 = 73$$$;
  • когда $$$k = 7$$$, вы можете переместить $$$6$$$-й элемент в конец, массив становится $$$[13, 5, 10, 14, 8, 13, 15]$$$, и значение, которое вы выводите, равно $$$13 + 5 + 10 + 14 + 8 + 13 + 15 = 78$$$.