C. Инкрементальное пребывание
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Danimal Cannon, Zef - The Lunar Whale
⠀

Вы — охранник музея.

Главная дверь музея является как входом, так и выходом. Через дверь может пройти не более одного человека каждую секунду. Существует датчик, который фиксирует, когда посетитель проходит через дверь. Датчик не может определить, кто именно посетитель, и вошел он или вышел из музея. Датчик зафиксировал некоторую активность в $$$2n$$$ различных моментах времени $$$a_1, a_2, \ldots, a_{2n}$$$ (измеряемых в секундах).

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

В данный момент музей закрыт (то есть в нем нет посетителей), и вам интересно, каково максимальное возможное общее время пребывания сегодня, т.е. максимальная возможная сумма времени пребывания всех посетителей, которые вошли в музей сегодня. В секунду $$$0$$$ музей также был закрыт.

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

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$), обозначающее, что датчик зафиксировал некоторую активность в $$$2n$$$ различных моментах времени.

Вторая строка каждого набора входных данных содержит $$$2n$$$ целых чисел $$$a_1, a_2, \ldots, a_{2n}$$$ ($$$1 \leq a_1 \lt a_2 \lt \ldots \lt a_{2n} \leq 10^9$$$) — секунды, когда датчик зафиксировал некоторую активность.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

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

Пример
Входные данные
3
1
32 78
2
4 5 6 9
4
6149048 26582657 36124499 43993239 813829899 860114890 910238130 913669539
Выходные данные
46 
4 6 
78018749 1737022233 1845329695 3385003015
Примечание

В первом наборе входных данных датчик зафиксировал активность в секунды $$$32$$$ и $$$78$$$. Напомним, что $$$k$$$ — это максимальное количество людей, которые могут одновременно находиться в музее.

  • Если $$$k$$$ равно $$$1$$$, то максимальное возможное общее время пребывания составляет $$$46$$$, если посетитель $$$1$$$ входит в $$$32$$$ секунду и выходит в $$$78$$$ секунду.

Во втором наборе входных данных датчик зафиксировал активность в секунды $$$4$$$, $$$5$$$, $$$6$$$ и $$$9$$$.

  • Если $$$k$$$ равно $$$1$$$, то максимальное возможное общее время пребывания составляет $$$4$$$, если посетитель $$$1$$$ входит в $$$4$$$ секунду и выходит в $$$5$$$ секунду, а посетитель $$$2$$$ входит в $$$6$$$ секунду и выходит в $$$9$$$ секунду.
  • Если $$$k$$$ равно $$$2$$$, то максимальное возможное общее время пребывания составляет $$$6$$$, если посетитель $$$1$$$ входит в $$$4$$$ секунду и выходит в $$$9$$$ секунду, а посетитель $$$2$$$ входит в $$$5$$$ секунду и выходит в $$$6$$$ секунду.