KOI 市由 $N$ 个交叉路口和 $N-1$ 条双向道路组成。你只能通过给定的道路在两个不同的交叉路口之间通行。换句话说，该市的道路网络构成了一棵树。道路位于二维平面上，且除了端点外，两条道路不会在其他位置相交。每条道路都有一个非负整数权重，代表通过该道路所需的时间。

KOI 市在几十年前还是一个小镇，但随着人口的涌入，它开始迅速扩张。在快速扩张的过程中，为了方便管理，市长将交叉路口编号为 $1$ 到 $N$。该编号系统满足以下性质：

• 交叉路口 $1$ 是城市的中心，且至少连接了 $2$ 条道路。
• 分配给交叉路口的编号构成了以交叉路口 $1$ 为根的树的一种先序遍历：对于任何子树，其根节点的编号是该子树中最小的编号。
• 对于每个交叉路口，考虑所有相邻（直接通过道路连接）的交叉路口中编号最小的一个。当你从这个交叉路口开始，按逆时针顺序排列所有相邻的交叉路口时，它们的编号是递增的。

随着大量人口涌入 KOI 市，交通拥堵问题日益严重。为了解决这个问题，市长用外环路连接了最外围的城市。设 $\{v_1, v_2, \dots, v_k\}$ 为所有恰好连接一条道路的交叉路口的编号，按递增顺序排列。对于每个 $1 \le i \le k$，市长在交叉路口 $v_i$ 和交叉路口 $v_{(i \bmod k)+1}$ 之间修建了一条双向道路。每条道路的权重为非负整数 $w_i$。由于编号系统的特性，你可以观察到，外环路可以在二维平面上添加，使得两条道路除了端点外在任何位置都不相交。

你正在尝试为 KOI 市构建一个导航系统。该导航系统需要回答 $Q$ 个形如 $(u, v)$ 的查询。对于每个查询，导航系统应返回从交叉路口 $u$ 到交叉路口 $v$ 所需的最短时间。通过路径移动的时间等于路径中各边权重的总和。

给定道路网络结构，编写一个程序来高效地回答 $Q$ 个查询。

输入格式

第一行包含 KOI 市的交叉路口数量 $N$ ($4 \le N \le 100\,000$)。

接下来的 $N-1$ 行，每行包含两个空格分隔的整数 $p_i$ 和 $c_i$。它们表示存在一条连接交叉路口 $p_i$ 和交叉路口 $i+1$ 的权重为 $c_i$ 的双向道路 ($1 \le p_i \le i, 0 \le c_i \le 10^{12}$)。

设 $k$ 为原树中恰好连接一条道路的交叉路口数量，设 $\{v_1, v_2, \dots, v_k\}$ 为它们编号的递增序列。下一行给出 $k$ 个空格分隔的整数 $w_1, w_2, \dots, w_k$。这表示连接交叉路口 $v_i$ 和交叉路口 $v_{(i \bmod k)+1}$ 的外环路权重为 $w_i$ ($0 \le w_i \le 10^{12}$)。

下一行包含查询数量 $Q$ ($1 \le Q \le 250\,000$)。

接下来的 $Q$ 行，每行包含两个整数 $u$ 和 $v$，表示感兴趣的交叉路口 ($1 \le u, v \le N$ 且 $u \neq v$)。

输出格式

对于每个查询，打印一行，包含一个整数：从 $u$ 到 $v$ 的最短移动时间。

样例

样例输入 1

4
1 9
1 8
1 0
9 9 9
6
1 2
1 3
1 4
2 3
2 4
3 4

样例输出 1

9
8
0
9
9
8

样例输入 2

11
1 9
1 8
3 0
4 7
4 1
3 6
1 0
8 7
8 1
10 6
0 0 0 0 0 0
21
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
7 1
8 2
9 3
10 4
11 5
1 6
2 7
3 8
4 9
5 10
6 11

样例输出 2

7
8
8
7
7
7
0
7
1
7
7
7
1
7
0
7
0
8
1
6
0

样例输入 3

11
1 9
1 8
3 0
4 7
4 1
3 6
1 0
8 7
8 1
10 6
1000000000000 1000000000000
1000000000000 1000000000000
1000000000000 1000000000000
21
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
7 1
8 2
9 3
10 4
11 5
1 6
2 7
3 8
4 9
5 10
6 11

样例输出 3

9
8
8
15
9
14
0
7
1
7
14
9
15
9
22
9
23
8
15
16
16

说明

在第三个样例中，包含 $w_1, w_2, \dots, w_k$ 的行（红色部分）为了可读性被拆分成了多行。

左图对应第一个样例。右图对应第二个和第三个样例。