Game with triangles

Even Little John needs money to buy a house. But he recently lost his job, so how will he earn money now? By playing a game that pays him as a reward, of course. Oh well, it is probably not the kind of game you are thinking of.

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 that are not collinear.
• Increase your score by the area of the triangle formed by these three points.
• 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 no operation is possible, $k\_{\max}$ is $0$. Define $f(k)$ as the maximum score achievable by performing the operation exactly $k$ times. $f(k)$ is defined for every integer $k$ with $0 \le k \le k\_{\max}$.

Find the value of $k\_{\max}$, and find the value of $f(x)$ for each integer $x=1,2,\ldots,k\_{\max}$.

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 test cases follow.

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 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 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$).

The sum of $n$ and the sum of $m$ over all test cases each do not exceed $2 \cdot 10^5$.

For each test case, output at most two lines.

The first line contains the value of $k\_{\max}$.

The second line contains $k\_{\max}$ integers $f(1),f(2),\ldots,f(k\_{\max})$. You may omit this line if $k\_{\max}$ is $0$.

Under the constraints of this problem, every value of $f(x)$ is an integer no greater than $10^{16}$.

In 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. So $k\_{\max}$ is $1$, and only $f(1)$ is asked.

You can choose $(0,0)$, $(-1,2)$, and $(1,2)$ as the three vertices. The triangle has area $2$, so your score increases by $2$ and the three points are erased. It can be shown that the maximum score after one operation is $2$. Therefore $f(1)=2$.

In the fifth test case, there are $8+2=10$ points. It can be shown that you cannot perform three or more operations. So $k\_{\max}$ is $2$, and $f(1)$ and $f(2)$ are asked.

To maximize the score with one operation, choose $(198\,872\,582,0)$, $(-1\,000\,000\,000,2)$, and $(1\,000\,000\,000,2)$. The score becomes $2\,000\,000\,000$, so $f(1)=2\,000\,000\,000$.

To maximize the score with exactly two operations, first choose $(-509\,489\,796,0)$, $(553\,177\,666,0)$, and $(-1\,000\,000\,000,2)$. Then choose $(-400\,714\,529,0)$, $(564\,040\,265,0)$, and $(1\,000\,000\,000,2)$. The score becomes $2\,027\,422\,256$, so $f(2)=2\,027\,422\,256$.