D. 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), \dots , (a\_{n},0), (b\_{1},2), (b\_{2},2), \dots, (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,\dots,k_{max}$ independently.

Input

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

Output

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

Example

Input

1
5
2
1 3
3
0
4
0 1 -1
5
2 4
6
0 100
7
-100 -50 0 50
8
2 4
9
0 1000
10
-100 -50 0 50
11
6 6
12
20 1 27 100 43 42
13
100 84 1 24 22 77
14
8 2
15
564040265 -509489796 469913620 198872582 -400714529 553177666 131159391 -20796763
16
-1000000000 1000000000

Output

1
1
2
2
3
2
4
150 200
5
2
6
1000 200
7
4
8
99 198 260 283
9
2
10
2000000000 2027422256

Note

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

Solution

1. 要构造满足非共线的三点，需要从 $y=0$ 的点中选 $2$ 个、$y=2$ 的点中选 $1$ 个，或反过来。
2. 每次选出的一组三点形成的三角形面积即对应行上选出的 $2$ 点的横坐标之差(因为高度为 $2$，$面积=\frac{1}{2}\times 底\times 高=差\times 1$)。
3. 先对 $y=0$ 的所有点进行排序，计算“前后配对”的最大差值之和形成前缀数组 $preA$；同理对 $y=2$ 的所有点生成前缀数组 $preB$。$preA[i]$ 表示恰好在 $y=0$ 行完成 $i$ 次“2点配对”操作的总最大面积，同理 $preB[i]$ 针对 $y=2$ 行。
4. 每次总共做 $k$ 次操作，需要在 $y=0$ 行做 $i$ 次、在 $y=2$ 行做 $(k - i)$ 次，要求 $2i+(k-i) \le n, i+2(k-i) \le m$。
5. 用三分搜索或其它方法在可行区间内寻找 $i$，使得 $preA[i] + preB[k-i]$ 最大，记为 $f(k)$。
6. 最后找出最大可行的 $k$ 值 $k\_{max}$，并输出 $f(1) \dots f(k\_{\max})$。

1
vector<int> buildPrefix(vector<int> &arr) {
2
  sort(arr.begin(), arr.end());
3
  int half = arr.size() / 2;
4
  vector<int> diff(half);
5
  for (int i = 0; i < half; i++) {
6
    diff[i] = arr[arr.size() - 1 - i] - arr[i];
7
  }
8
  sort(diff.begin(), diff.end(), greater<int>());
9
  vector<int> prefix(half + 1, 0LL);
10
  for (int i = 1; i <= half; i++) {
11
    prefix[i] = prefix[i - 1] + diff[i - 1];
12
  }
13
  return prefix;
14
}
15

16
int ternaryMax(const vector<int> &A, const vector<int> &B, int k, int low,
17
               int high) {
18
  if (low > high) return 0;
19
  auto G = [&](int x) { return A[x] + B[k - x]; };
20
  while (high - low >= 3) {
21
    int m1 = low + (high - low) / 3;
22
    int m2 = high - (high - low) / 3;
23
    if (G(m1) < G(m2))
24
      low = m1 + 1;
25
    else
26
      high = m2 - 1;
27
  }
28
  int ret = 0;
29
  for (int i = low; i <= high; i++) {
30
    ret = max(ret, G(i));
31
  }
32
  return ret;
33
}
34

35
void solve() {
36
  int n, m;
37
  cin >> n >> m;
38
  vector<long long> a(n), b(m);
39
  for (int i = 0; i < n; i++) {
40
    cin >> a[i];
41
  }
42
  for (int j = 0; j < m; j++) {
43
    cin >> b[j];
44
  }
45

46
  vector<long long> preA = buildPrefix(a);
47
  vector<long long> preB = buildPrefix(b);
48
  int maxPickA = (int)preA.size() - 1;
49
  int maxPickB = (int)preB.size() - 1;
50
  int kmax = min((n + m) / 3LL, (long long)maxPickA + maxPickB);
51
  vector<long long> f(kmax + 1, 0LL);
52

53
  for (int k = 1; k <= kmax; k++) {
54
    // i的可行区间
55
    // 要满足 i + (k−i) = k，2*i + (k−i) <= n => i <= n-k
56
    //           i + 2*(k−i) <= m => i >= 2*k - m
57
    // 同时 i >= 0, i <= k, i <= maxPickA, k−i <= maxPickB
58
    int low = max(0LL, (int)max((long long)k - maxPickB, 2LL * k - m));
59
    int high = min(k, min(maxPickA, n - k));
60
    if (low <= high) {
61
      auto bestVal = ternaryMax(preA, preB, k, low, high);
62
      f[k] = bestVal;
63
    }
64
  }
65

66
  while (kmax > 0 && f[kmax] == 0) kmax--;
67

68
  cout << kmax << endl;
69
  if (kmax > 0) {
70
    for (int i = 1; i <= kmax; i++) {
71
      cout << f[i] << (i < kmax ? ' ' : '\n');
72
    }
73
  }
74
}
75

76
signed main() {
77
  setIO();
78
  int tt = 1;
79
  cin >> tt;
80
  while (tt--) {
81
    solve();
82
  }
83
  return 0;
84
}