33313번 - 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円$.