该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

给定一个点集，$q$ 次询问，每次询问给三个点，求以其中一点为顶点且过另外两点的覆盖点集的最小面积矩形的面积。

保证给定的点集坐标随机。

Format

Input

第一行一个正整数 $n(1\le n\le 10^6)$ 表示点集大小。

第二行 $n$ 个整整分别表示第 $i$ 个点的 $x$ 坐标 $x_i(-10^9\le x_i\le 10^9)$。

第三行 $n$ 个整数分别表示第 $i$ 个点的 $y$ 坐标 $y_i(-10^9\le y_i\le 10^9)$。

第四行一个正整数 $q(1\le q\le 2\times 10^5)$ 表示询问次数。

接下来 $q$ 行，每行六个整数 $x_1,y_1,x_2,y_2,x_3,y_3(-10^9\le x_1,x_2,x_3,y_1,y_2,y_3\le 10^9)$ 分别表示询问的三个点的坐标。

Output

共 $q$ 行，每行一个整数表示覆盖点集的最小面积矩形的面积。

Samples

123 500

623

Note

牛客小白月赛 F

2025 zstu 校赛 hard