Game With Triangles

Even Little John needs money to buy a house. But he recently lost his job; how will he earn money now? Of course, by playing a game that gives him money as a reward! Oh well, maybe not those kinds of games you are thinking about.

There are $n+m$ distinct points $(a_1,0), (a_2,0), \ldots, (a_{n},0), (b_1,2), (b_2,2), \ldots, (b_{m},2)$ on the plane. Initially, your score is $0$. To increase your score, you can perform the following operation:

• Choose three distinct points which are not collinear;
• Increase your score by the area of the triangle formed by these three points;
• Then, erase the three points from the plane.

An instance of the game, where the operation is performed twice.

Let $k_{\max}$ be the maximum number of operations that can be performed. For example, if it is impossible to perform any operation, $k_\max$ is $0$. Additionally, define $f(k)$ as the maximum possible score achievable by performing the operation exactly $k$ times. Here, $f(k)$ is defined for all integers $k$ such that $0 \le k \le k_{\max}$.

Find the value of $k_{\max}$, and find the values of $f(x)$ for all integers $x=1,2,\ldots,k_{\max}$ independently.

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 3 \cdot 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($1 \le n,m \le 2 \cdot 10^5$).

The second line of each test case contains $n$ pairwise distinct integers $a_1,a_2,\ldots,a_{n}$ --- the points on $y=0$ ($-10^9 \le a_i \le 10^9$).

The third line of each test case contains $m$ pairwise distinct integers $b_1,b_2,\ldots,b_{m}$ --- the points on $y=2$ ($-10^9 \le b_i \le 10^9$).

It is guaranteed that both the sum of $n$ and the sum of $m$ over all test cases do not exceed $2 \cdot 10^5$.

For each test case, given that the maximum number of operations is $k_{\max}$, you must output at most two lines:

• The first line contains the value of $k_{\max}$;
• The second line contains $k_{\max}$ integers denoting $f(1),f(2),\ldots,f(k_{\max})$. You are allowed to omit this line if $k_{\max}$ is $0$.

Note that under the constraints of this problem, it can be shown that all values of $f(x)$ are integers no greater than $10^{16}$.

On the first test case, there are $1+3=4$ points $(0,0),(0,2),(1,2),(-1,2)$.

It can be shown that you cannot perform two or more operations. The value of $k_{\max}$ is $1$, and you are only asked for the value of $f(1)$.

You can choose $(0,0)$, $(-1,2)$, and $(1,2)$ as the three vertices of the triangle. After that, your score is increased by the area of the triangle, which is $2$. Then, the three points are erased from the plane. It can be shown that the maximum value of your score after performing one operation is $2$. Therefore, the value of $f(1)$ is $2$.

On the fifth test case, there are $8+2=10$ points.

It can be shown that you cannot perform three or more operations. The value of $k_{\max}$ is $2$, and you are asked for the values $f(1)$ and $f(2)$.

To maximize the score with only one operation, you can choose three points $(198\,872\,582,0)$, $(-1\,000\,000\,000,2)$, and $(1\,000\,000\,000,2)$. Then, the three points are erased from the plane. It can be shown that the maximum value of your score after performing one operation is $2\,000\,000\,000$. Therefore, the value of $f(1)$ is $2\,000\,000\,000$.

To maximize the score with exactly two operations, you can choose the following sequence of operations.

• Choose three points $(-509\,489\,796,0)$, $(553\,177\,666,0)$, and $(-1\,000\,000\,000,2)$. The three points are erased.
• Choose three points $(-400\,714\,529,0)$, $(564\,040\,265,0)$, and $(1\,000\,000\,000,2)$. The three points are erased.

Then, the score after two operations becomes $2\,027\,422\,256$. It can be shown that the maximum value of your score after performing exactly two operations is $2\,027\,422\,256$. Therefore, the value of $f(2)$ is $2\,027\,422\,256$.