D. Game With Trianglestime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output 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.InputEach 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$$$.OutputFor 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}$$$.ExampleInput51 300 1 -12 40 100-100 -50 0 502 40 1000-100 -50 0 506 620 1 27 100 43 42100 84 1 24 22 778 2564040265 -509489796 469913620 198872582 -400714529 553177666 131159391 -20796763-1000000000 1000000000Output1
2
2
150 200
2
1000 200
4
99 198 260 283
2
2000000000 2027422256
NoteOn 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$$$.