JOI 国的 $N$ 个城市编号为 $1$ 到 $N$。共有 $N-1$ 条道路，编号为 $1$ 到 $N-1$。第 $i$ 条道路（$1 \le i \le N-1$）包含两条车道：一条是从城市 $A_i$ 到城市 $B_i$ 的车道，另一条是从城市 $B_i$ 到城市 $A_i$ 的车道。因此，所有道路都是双向的。通过道路可以在任意两个城市之间通行。

目前，所有道路的所有车道都未铺设。对于每条道路的每条车道，我们已知铺设该车道的费用。对于第 $i$ 条道路（$1 \le i \le N-1$），从城市 $A_i$ 到城市 $B_i$ 的车道铺设费用为 $C_i$，从城市 $B_i$ 到城市 $A_i$ 的车道铺设费用为 $D_i$。

JOI 国首相 K 先生可以选择一些城市并将它们指定为度假城市。当他将城市 $x$（$1 \le x \le N$）指定为度假城市时，对于每条道路 $i$（$1 \le i \le N-1$），会发生以下事件：

在城市 $A_i$ 和 $B_i$ 中，设 $a$ 为距离城市 $x$ 较近的城市，设 $b$ 为较远的城市。这里，距离城市 $x$ 较近的城市是指从该城市出发，经过最少数量的道路即可到达城市 $x$ 的城市。然后，从城市 $b$ 到城市 $a$ 的车道将被铺设（如果尚未铺设）。

因指定度假城市而产生的车道铺设工程费用将由税收支付。然而，指定后仍未铺设的车道，其铺设工程费用需要由 K 先生自掏腰包支付。

K 先生收到了 $Q$ 个方案。在第 $j$ 个方案（$1 \le j \le Q$）中，他从没有度假城市且所有道路的所有车道均未铺设的情况开始，并指定恰好 $E_j$ 个城市作为度假城市。然而，具体指定哪些城市尚未确定。他想知道对于每个方案，需要从他个人腰包中支付的最小总铺设费用。

编写一个程序，给定 JOI 国的城市数量、道路信息以及方案信息，计算每个方案中需要由 K 先生个人支付的最小总铺设费用。

输入格式

从标准输入读取以下数据。所有输入值均为整数。

$N$ $A_1$ $B_1$ $C_1$ $D_1$ $\vdots$ $A_{N-1}$ $B_{N-1}$ $C_{N-1}$ $D_{N-1}$ $Q$ $E_1$ $\vdots$ $E_Q$

输出格式

向标准输出打印 $Q$ 行。第 $j$ 行（$1 \le j \le Q$）应包含第 $j$ 个方案中需要由 K 先生个人支付的最小总铺设费用。

数据范围

• $2 \le N \le 200\,000$
• $1 \le A_i \le N$ ($1 \le i \le N-1$)
• $1 \le B_i \le N$ ($1 \le i \le N-1$)
• $A_i \neq B_i$ ($1 \le i \le N-1$)
• 任意两个城市之间均可通过道路通行。
• $1 \le C_i \le 1\,000\,000\,000$ ($1 \le i \le N-1$)
• $1 \le D_i \le 1\,000\,000\,000$ ($1 \le i \le N-1$)
• $1 \le Q \le N$
• $1 \le E_j \le N$ ($1 \le j \le Q$)

子任务

1. (6 分) $N \le 16$
2. (7 分) $Q = 1, E_1 = 1$
3. (9 分) $Q = 1, E_1 = 2$
4. (17 分) $N \le 2\,000$
5. (17 分) $Q = 1$
6. (44 分) 无附加限制

样例

样例输入 1

4
1 2 1 2
1 3 3 4
1 4 5 6
2
1
2

样例输出 1

9
1

说明 1

考虑方案 1：K 先生将指定恰好 1 个城市作为度假城市。如果他将城市 1 指定为度假城市，则道路 1 从城市 2 到城市 1 的车道、道路 2 从城市 3 到城市 1 的车道以及道路 3 从城市 4 到城市 1 的车道将被铺设。因此，以下车道将保持未铺设：道路 1 从城市 1 到城市 2 的车道、道路 2 从城市 1 到城市 3 的车道以及道路 3 从城市 1 到城市 4 的车道。这些车道的总铺设费用为 $1 + 3 + 5 = 9$。没有办法指定一个城市使得总费用小于 9。因此，答案是 9。

考虑方案 2：K 先生将指定恰好 2 个城市作为度假城市。如果他将城市 3 和城市 4 指定为度假城市，则道路 1 从城市 1 到城市 2 的车道将是唯一保持未铺设的车道。铺设该车道的费用为 1。没有办法指定 2 个城市使得总费用小于 1。因此，答案是 1。

样例输入 2

5
1 3 13 6
5 1 17 8
5 2 6 10
1 4 16 11
1
1

样例输出 2

36

说明 2

此样例输入满足子任务 2 的限制。

样例输入 3

6
1 6 6 12
6 2 5 16
1 4 13 4
5 1 19 3
3 1 9 13
1
2

样例输出 3

14

说明 3

此样例输入满足子任务 3 的限制。

样例输入 4

15
14 5 12 7
14 12 6 5
14 10 14 16
9 14 16 12
13 7 4 15
1 3 8 1
6 7 15 13
15 4 4 6
9 1 12 6
13 1 7 6
13 4 5 15
2 6 11 19
8 4 12 7
13 11 14 5
3
3
6
7

样例输出 4

44
12
6