D. Игра с треугольниками
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Даже маленькому Джону нужны деньги, чтобы купить дом. Но он недавно потерял работу; как же он теперь заработает деньги? Конечно, играя в игру, которая дает ему деньги в качестве награды! Ну, может быть, не в те игры, о которых вы думаете.

На плоскости есть $$$n+m$$$ различных точек $$$(a_1,0), (a_2,0), \ldots, (a_{n},0), (b_1,2), (b_2,2), \ldots, (b_{m},2)$$$. Изначально ваш счет равен $$$0$$$. Чтобы увеличить свой счет, вы можете выполнить следующую операцию:

  • Выберите три различные точки, которые не лежат на одной прямой.
  • Увеличьте свой счет на площадь треугольника, образованного этими тремя точками.
  • Затем удалите три точки с плоскости.
Пример игры, где операция выполняется дважды.

Пусть $$$k_{\max}$$$ — максимальное количество операций, которое можно выполнить. Например, если нельзя выполнить эту операцию ни разу, то $$$k_\max$$$ равно $$$0$$$. Кроме того, определим $$$f(k)$$$ как максимальный возможный счет, который можно получить, выполнив операцию ровно $$$k$$$ раз. Здесь $$$f(k)$$$ определено для всех целых чисел $$$k$$$, таких что $$$0 \le k \le k_{\max}$$$.

Найдите значение $$$k_{\max}$$$ и найдите значения $$$f(x)$$$ для всех целых чисел $$$x=1,2,\ldots,k_{\max}$$$ независимо.

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

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

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n,m \le 2 \cdot 10^5$$$).

Вторая строка каждого набора входных данных содержит $$$n$$$ попарно различных целых чисел $$$a_1,a_2,\ldots,a_{n}$$$ — точки на $$$y=0$$$ ($$$-10^9 \le a_i \le 10^9$$$).

Третья строка каждого набора входных данных содержит $$$m$$$ попарно различных целых чисел $$$b_1,b_2,\ldots,b_{m}$$$ — точки на $$$y=2$$$ ($$$-10^9 \le b_i \le 10^9$$$).

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

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

Для каждого набора входных данных, учитывая, что максимальное количество операций равно $$$k_{\max}$$$, вы должны вывести не более двух строк:

  • Первая строка содержит значение $$$k_{\max}$$$;
  • Вторая строка содержит $$$k_{\max}$$$ целых числа, обозначающих $$$f(1),f(2),\ldots,f(k_{\max})$$$. Вы можете опустить эту строку, если $$$k_{\max}$$$ равно $$$0$$$.

Обратите внимание, что в условиях этой задачи можно показать, что все значения $$$f(x)$$$ являются целыми числами, не превышающими $$$10^{16}$$$.

Пример
Входные данные
5
1 3
0
0 1 -1
2 4
0 100
-100 -50 0 50
2 4
0 1000
-100 -50 0 50
6 6
20 1 27 100 43 42
100 84 1 24 22 77
8 2
564040265 -509489796 469913620 198872582 -400714529 553177666 131159391 -20796763
-1000000000 1000000000
Выходные данные
1
2
2
150 200
2
1000 200
4
99 198 260 283
2
2000000000 2027422256
Примечание

В первом наборе входных данных есть $$$1+3=4$$$ точки $$$(0,0),(0,2),(1,2),(-1,2)$$$.

Можно показать, что вы не можете выполнить две или более операций. Значение $$$k_{\max}$$$ равно $$$1$$$, и вас просят только о значении $$$f(1)$$$.

Вы можете выбрать $$$(0,0)$$$, $$$(-1,2)$$$ и $$$(1,2)$$$ в качестве трех вершин треугольника. После этого ваш счет увеличивается на площадь треугольника, которая равна $$$2$$$. Затем три точки удаляются с плоскости. Можно показать, что максимальное значение вашего счета после выполнения одной операции равно $$$2$$$. Следовательно, значение $$$f(1)$$$ равно $$$2$$$.

В пятом наборе входных данных есть $$$8+2=10$$$ точек.

Можно показать, что вы не можете выполнить три или более операций. Значение $$$k_{\max}$$$ равно $$$2$$$, и вас просят о значениях $$$f(1)$$$ и $$$f(2)$$$.

Чтобы максимизировать счет с помощью только одной операции, вы можете выбрать три точки $$$(198\,872\,582,0)$$$, $$$(-1\,000\,000\,000,2)$$$ и $$$(1\,000\,000\,000,2)$$$. Затем три точки удаляются с плоскости. Можно показать, что максимальное значение вашего счета после выполнения одной операции равно $$$2\,000\,000\,000$$$. Следовательно, значение $$$f(1)$$$ равно $$$2\,000\,000\,000$$$.

Чтобы максимизировать счет с помощью ровно двух операций, вы можете выбрать следующую последовательность операций.

  • Выберите три точки $$$(-509\,489\,796,0)$$$, $$$(553\,177\,666,0)$$$ и $$$(-1\,000\,000\,000,2)$$$. Три точки удаляются.
  • Выберите три точки $$$(-400\,714\,529,0)$$$, $$$(564\,040\,265,0)$$$ и $$$(1\,000\,000\,000,2)$$$. Три точки удаляются.

Тогда счет после двух операций становится $$$2\,027\,422\,256$$$. Можно показать, что максимальное значение вашего счета после выполнения ровно двух операций равно $$$2\,027\,422\,256$$$. Следовательно, значение $$$f(2)$$$ равно $$$2\,027\,422\,256$$$.