F. Задача котовояжёра
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы — кот, продающий интересные алгоритмические задачи. Сегодня вы хотите прорекламировать свои интересные алгоритмические задачи в $$$k$$$ городах.

Всего есть $$$n$$$ городов, каждый из которых имеет два параметра $$$a_i$$$ и $$$b_i$$$. Между любыми двумя городами $$$i,j$$$ ($$$i\ne j$$$) есть двусторонняя дорога длиной $$$\max(a_i + b_j , b_i + a_j)$$$. Стоимость пути определяется как сумма длин дорог между каждыми двумя соседними городами вдоль пути.

Для $$$k=2,3,\ldots,n$$$ найдите минимальную стоимость среди всех простых путей, содержащих ровно $$$k$$$ различных городов.

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \leq n \leq 3\cdot 10^3$$$) — количество городов.

Затем следуют $$$n$$$ строк, $$$i$$$-я строка содержит два целых числа $$$a_i,b_i$$$ ($$$0 \leq a_i,b_i \leq 10^9$$$) — параметры города $$$i$$$.

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

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

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

Пример
Входные данные
3
3
0 2
2 1
3 3
5
2 7
7 5
6 3
1 8
7 5
8
899167687 609615846
851467150 45726720
931502759 23784096
918190644 196992738
142090421 475722765
409556751 726971942
513558832 998277529
294328304 434714258
Выходные данные
4 9 
10 22 34 46 
770051069 1655330585 2931719265 3918741472 5033924854 6425541981 7934325514
Примечание

В первом наборе входных данных:

  • Для $$$k=2$$$ оптимальный путь: $$$1\to 2$$$ со стоимостью $$$\max(0+1,2+2)=4$$$.
  • Для $$$k=3$$$ оптимальный путь: $$$2\to 1\to 3$$$ со стоимостью $$$\max(0+1,2+2)+\max(0+3,3+2)=4+5=9$$$.

Во втором наборе входных данных:

  • Для $$$k=2$$$ оптимальный путь: $$$1\to 4$$$.
  • Для $$$k=3$$$ оптимальный путь: $$$2\to 3\to 5$$$.
  • Для $$$k=4$$$ оптимальный путь: $$$4\to 1\to 3\to 5$$$.
  • Для $$$k=5$$$ оптимальный путь: $$$5\to 2\to 3\to 1\to 4$$$.