题目描述

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 国总理 Mr. K 可选择若干城市并将其指定为 度假城市。当他将城市 $x$（$1 \le x \le N$）指定为度假城市时，以下事件将对每条道路 $i$（$1 \le i \le N - 1$）发生：

在城市 $A_i$ 与 $B_i$ 中，设 $a$ 为距离城市 $x$ 更近的城市，$b$ 为距离城市 $x$ 更远的城市。此处，“距离城市 $x$ 更近”是指从该城市出发，到达城市 $x$ 所需经过的道路数量更少。随后，从城市 $b$ 指向城市 $a$ 的车道将被铺设（若尚未铺设）。

因指定度假城市而产生的车道铺设费用将由税收支付。然而，指定后仍保持未铺设状态的车道的铺设费用需由 Mr. K 自掏腰包支付。

现共有 $Q$ 个方案提交给 Mr. K。在第 $j$ 个方案（$1 \le j \le Q$）中，他将从无任何度假城市、且所有道路的所有车道均未铺设的初始状态出发，并恰好指定 $E_j$ 座城市为度假城市。但具体指定哪些城市尚未确定。他希望知道，对于每个方案，需由他自掏腰包支付的最小总铺设费用是多少。

请编写一个程序，输入 JOI 国的城市数量、道路信息及各方案信息，计算并输出每个方案中需由 Mr. 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$ 个方案中需由 Mr. K 自掏腰包支付的最小总铺设费用。

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

9
1

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

14

提示

样例 1 解释

考虑方案 1：Mr. 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：Mr. K 将恰好指定 2 座城市为度假城市。若他指定城市 3 和城市 4 为度假城市，则道路 1 上从城市 1 指向城市 2 的车道将是唯一保持未铺设的车道。铺设该车道的成本为 1。不存在任何指定 2 座城市的方式能使总成本低于 1。因此，答案为 1。

约束条件

• $2 \le N \le 200000$。
• $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 \ne B_i$（$1 \le i \le N - 1$）。
• 任意两座城市之间均可通过道路相互到达。
• $1 \le C_i \le 1000000000$（$1 \le i \le N - 1$）。
• $1 \le D_i \le 1000000000$（$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 2000$。
5. （17 分）$Q = 1$。
6. （44 分）无额外约束。