B. Треугольники на прямоугольнике
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На плоскости нарисован прямоугольник с противоположными углами в $$$(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$$$.

В следующих двух строках содержится описание точек на вертикальных сторонах. Сначала целое число $$$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$$$.

Суммарное количество точек на всех сторонах во всех наборах входных данных не превышает $$$2 \cdot 10^5$$$.

Выходные данные

На каждый набор входных данных выведите одно целое число — удвоенную максимальную площадь треугольника, образованного такими тремя точками, что ровно две из них лежат на одной и той же стороне.

Пример
Входные данные
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
Выходные данные
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)$$$.