即使是小约翰也需要钱买房子。但他最近失业了;他现在怎么赚钱呢?当然是玩一个给他钱作为奖励的游戏!哦,好吧,也许不是您正在考虑的那种游戏。
平面上有 $$$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}$$$ 的值,并独立找到所有整数 $$$x=1,2,\ldots,k_{\max}$$$ 的 $$$f(x)$$$ 的值。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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}$$$的整数。
示例
输入 #1
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
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$$$。