삼각형 게임

Little John은 집을 사려면 돈이 필요하다. 그런데 최근에 일자리를 잃었다. 그러면 이제 어떻게 돈을 벌까? 당연히 보상으로 돈을 주는 게임을 하면 된다. 다만 아마 여러분이 떠올린 그런 게임은 아닐 것이다.

평면 위에 서로 다른 $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)$는 $0 \le k \le k\_{\max}$인 모든 정수 $k$에 대해 정의된다.

$k\_{\max}$의 값을 구하고, $x=1,2,\ldots,k\_{\max}$인 각 정수 $x$에 대해 $f(x)$의 값을 구하라.

각 입력에는 여러 개의 테스트 케이스가 들어 있다. 첫 줄에는 테스트 케이스의 개수 $t$ ($1 \le t \le 3 \cdot 10^4$)가 주어진다. 테스트 케이스가 이어진다.

각 테스트 케이스의 첫 줄에는 정수 $n$과 $m$ ($1 \le n,m \le 2 \cdot 10^5$)이 주어진다.

둘째 줄에는 $y=0$ 위의 점인 서로 다른 정수 $n$개 $a\_1,a\_2,\ldots,a\_{n}$ ($-10^9 \le a\_i \le 10^9$)이 주어진다.

셋째 줄에는 $y=2$ 위의 점인 서로 다른 정수 $m$개 $b\_1,b\_2,\ldots,b\_{m}$ ($-10^9 \le b\_i \le 10^9$)이 주어진다.

모든 테스트 케이스에서 $n$의 합과 $m$의 합은 각각 $2 \cdot 10^5$를 넘지 않는다.

각 테스트 케이스마다 최대 두 줄을 출력한다.

첫 줄에는 $k\_{\max}$의 값을 출력한다.

둘째 줄에는 $k\_{\max}$개의 정수 $f(1),f(2),\ldots,f(k\_{\max})$를 출력한다. $k\_{\max}$가 $0$이면 이 줄은 생략해도 된다.

이 문제의 제약에서 모든 $f(x)$ 값은 $10^{16}$ 이하의 정수임이 보장된다.

첫 번째 테스트 케이스에는 $1+3=4$개의 점 $(0,0),(0,2),(1,2),(-1,2)$가 있다. 연산을 두 번 이상 수행할 수 없음을 보일 수 있다. 따라서 $k\_{\max}$는 $1$이고, 구해야 하는 값은 $f(1)$뿐이다.

세 꼭짓점으로 $(0,0)$, $(-1,2)$, $(1,2)$를 고를 수 있다. 이 삼각형의 넓이는 $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$이 되므로 $f(2)=2\,027\,422\,256$이다.