在平面上绘制一个矩形,其对角位于 $$$(0, 0)$$$ 和 $$$(w, h)$$$ 且边平行于轴。
给你一个格点列表,每个点都位于矩形的一边,但不在其角上。此外,矩形的每条边上至少有两个点。
您的任务是选择三个点,以便:
- 其中两个恰好属于矩形的同一边;
- 由它们形成的三角形面积是最大可能的。
打印该三角形的两倍面积。可以证明,由格点构成的任意三角形的两倍面积始终是整数。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含两个整数 $$$w$$$ 和 $$$h$$$ ($$$3 \le w, h \le 10^6$$$) - 矩形角的坐标。
接下来的两行包含两个水平边上的点的描述。首先,一个整数 $$$k$$$ ($$$2 \le k \le 2 \cdot 10^5$$$) — 点数。然后,$$$k$$$ 整数 $$$x_1 < x_2 < \dots < x_k$$$ ($$$0 < x_i < w$$$) - 按升序排列的点的 $$$x$$$ 坐标。第一行的 $$$y$$$ 坐标是 $$$0$$$,第二行的 $$$h$$$ 坐标是 $$$h$$$。
接下来的两行包含两个垂直边上的点的描述。首先,一个整数 $$$k$$$ ($$$2 \le k \le 2 \cdot 10^5$$$) — 点数。然后,$$$k$$$ 整数 $$$y_1 < y_2 < \dots < y_k$$$ ($$$0 < y_i < h$$$) — 按升序排列的点的 $$$y$$$ 坐标。第一行的 $$$x$$$ 坐标是 $$$0$$$,第二行的 $$$w$$$ 坐标是 $$$w$$$。
所有测试用例中所有边的点数总数不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - 由这三个点形成的三角形的最大面积的两倍,其中恰好有两个点属于同一边。
示例
输入 #1
3 5 8 2 1 2 3 2 3 4 3 1 4 6 2 4 5 10 7 2 3 9 2 1 7 3 1 3 4 3 4 5 6 11 5 3 1 6 8 3 3 6 8 3 1 3 4 2 2 4
输出 #1
25 42 35
注意
示例第一个测试用例中的要点:
- $$$(1, 0)$$$, $$$(2, 0)$$$;
- $$$(2, 8)$$$, $$$(3, 8)$$$, $$$(4, 8)$$$;
- $$$(0, 1)$$$, $$$(0, 4)$$$, $$$(0, 6)$$$;
- $$$(5, 4)$$$, $$$(5, 5)$$$.
最大的三角形由点 $$$(0, 1)$$$、$$$(0, 6)$$$ 和 $$$(5, 4)$$$ 形成 - 其面积为 $$$\frac{25}{2}$$$。因此,加倍的面积为 $$$25$$$。位于同一侧的两个点是:$$$(0, 1)$$$ 和 $$$(0, 6)$$$。