Description

在联盟多校的第5场，有一道题叫最近中继，贪吃佘写这题时不幸看错了题面，于是诞生了这道题。

一条笔直的地下通道中有 $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$；
• 任选一个中继站$z$,支付 $c_z$ 单位能量，启动中继站 $z$，并立即移动到距离 $z$ 最近的中继站。

现在有 $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

4
9
3
4
13

Note

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

需要注意的是，启动中继站 $z$ 时，当前位置不必为 $z$。无论当前位于哪个中继站，都可以支付 $c_z$ 单位能量启动中继站 $z$，随后立即移动到距离 $z$ 最近的中继站。

对于第一个询问 $1 \to 4$，可以按照以下方式移动：

• 启动中继站 $2$，花费 $c_2=1$ 单位能量，并移动到距离中继站 $2$ 最近的中继站 $3$；
• 从中继站 $3$ 普通移动到中继站 $4$，花费 $a_4-a_3=15-12=3$ 单位能量。

总费用为 $1+3=4$。

对于第二个询问 $1 \to 5$，可以按照以下方式移动：

• 启动中继站 $2$，花费 $c_2=1$ 单位能量，并移动到中继站 $3$；
• 从中继站 $3$ 普通移动到中继站 $5$，花费 $a_5-a_3=20-12=8$ 单位能量。

总费用为 $1+8=9$。

对于第三个询问 $3 \to 4$，直接从中继站 $3$ 移动到中继站 $4$，费用为 $a_4-a_3=15-12=3$。

对于第四个询问 $3 \to 2$，直接从中继站 $3$ 移动到中继站 $2$，费用为 $a_3-a_2=12-8=4$。

对于第五个询问 $5 \to 1$，可以按照以下方式移动：

• 启动中继站 $2$，花费 $c_2=1$ 单位能量，并移动到中继站 $3$；
• 从中继站 $3$ 普通移动到中继站 $1$，花费 $a_3-a_1=12-0=12$ 单位能量。

总费用为 $1+12=13$。