Description

一条笔直的地下通道中有 $n$ 个中继站。第 $i$ 个中继站位于坐标 $a_i$，并且 $a_1 < a_2 < \dots < a_n$。

两个中继站 $x$ 和 $y$ 之间的距离为 $|a_x-a_y|$。

对于每个中继站 $i$，距离它最近的另一个中继站是唯一的。换言之，不存在两个不同的中继站与中继站 $i$ 的距离相同且同时达到最小值。

第 $i$ 个中继站还有一个启动费用 $c_i$。

当你位于中继站 $x$ 时，可以执行任意次以下操作：

• 选择任意另一个中继站 $y$，支付 $|a_x-a_y|$ 单位能量并移动到中继站 $y$；
• 支付 $c_x$ 单位能量，启动中继站 $x$，并立即移动到距离 $x$ 最近的中继站。

现在有 $q$ 个相互独立的询问。每个询问给出两个不同的中继站 $x$ 和 $y$，你需要求出从 $x$ 到达 $y$ 所需的最少能量。

Format

Input

第一行包含一个整数 $t$（$1\le t\le 10^4$），表示测试用例的数量。

每个测试用例包含以下内容。

第一行包含一个整数 $n$（$2\le n\le 2\cdot 10^5$），表示中继站的数量。

第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$（$0\le a_1 < a_2 < \dots < a_n \le 10^{18}$），表示各中继站的坐标。

第三行包含 $n$ 个整数 $c_1,c_2,\dots,c_n$（$1\le c_i \le 10^{18}$），其中 $c_i$ 表示启动中继站 $i$ 的费用。

第四行包含一个整数 $q$（$1\le q\le 2\cdot 10^5$），表示询问数量。

接下来 $q$ 行，每行包含两个整数 $x$ 和 $y$（$1\le x,y\le n$，$x\ne y$），表示一个从中继站 $x$ 到中继站 $y$ 的询问。

保证每个中继站距离最近的另一个中继站是唯一的。

保证所有测试用例中 $n$ 的总和不超过 $2\cdot 10^5$，所有测试用例中 $q$ 的总和不超过 $2\cdot 10^5$。

Output

对于每个询问，输出一行一个整数，表示从中继站 $x$ 到中继站 $y$ 所需的最少能量。

Samples

1
5
0 8 12 15 20
7 1 10 2 4
5
1 4
1 5
3 4
3 2
5 1

11
16
3
4
18

Note

五个中继站的最近中继分别为 $2,3,4,3,4$。

对于第一个询问，可以按照以下方式移动：

• 从站点 $1$ 启动中继并前往站点 $2$，费用为 $7$；
• 从站点 $2$ 启动中继并前往站点 $3$，费用为 $1$；
• 从站点 $3$ 普通移动到站点 $4$，费用为 $3$。

总费用为 $7+1+3=11$。

注意，站点 $3$ 的启动费用为 $10$，大于它与站点 $4$ 之间的距离 $3$，因此此处使用普通移动更优。