특별관광도시

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$번 도로의 $A_i$번 도시에서 $B_i$번 도시로 가는 노선을 정비하는 비용은 $C_i$이고, $B_i$번 도시에서 $A_i$번 도시로 가는 노선을 정비하는 비용은 $D_i$이다.

장관 K는 몇몇 도시를 특별관광도시로 만든다. 도시 $x$ ($1 \le x \le N$)를 특별관광도시로 만들면, 각 도로 $i$ ($1 \le i \le N-1$)에 대해 다음 일이 일어난다. $A_i$번과 $B_i$번 도시 중 $x$번 도시에 가까운 도시를 $a$번, 먼 도시를 $b$번이라 하자. 여기서 가깝다는 것은 $x$번 도시에서 그 도시까지 거쳐야 하는 도로 수가 적다는 뜻이다. $b$번 도시에서 $a$번 도시로 가는 노선이 아직 정비되지 않았다면, 그 노선을 정비한다.

특별관광도시를 만들면서 드는 정비 비용은 세금으로 충당한다. 특별관광도시를 만든 뒤에 하는 정비 비용은 K의 개인 자금에서 나간다.

K는 $Q$개의 계획을 세웠다. $j$번째 ($1 \le j \le Q$) 계획에서 K는 특별관광도시가 하나도 없고 모든 노선이 정비되지 않은 상태에서 시작해, 정확히 $E_j$개의 도시를 특별관광도시로 만든다. 어떤 도시를 고를지는 정해져 있지 않다. K는 개인 자금에서 나가는 정비 비용을 최소로 하고 싶어 한다. 도시 수, 도로 정보, 계획 정보가 주어졌을 때, 각 계획마다 개인 자금에서 나가는 정비 비용의 최솟값을 구하는 프로그램을 작성하여라.

첫째 줄에 $N$이 주어진다. 다음 $N-1$개의 줄에는 각각 $A_i$, $B_i$, $C_i$, $D_i$가 주어진다. 그다음 줄에는 $Q$가 주어진다. 다음 $Q$개의 줄에는 각각 $E_j$가 주어진다.

$Q$개의 줄을 출력한다. $j$번째 줄에는 $j$번째 계획에서 개인 자금으로 치르는 정비 비용의 최솟값을 출력한다.

$2 \le N \le 200\ 000$. $1 \le A_i \le N$ ($1 \le i \le N$). $1 \le B_i \le N$ ($1 \le i \le N$). $A_i \ne B_i$ ($1 \le i \le N$). 어떤 두 도시든 도로를 몇 개 거쳐 이동할 수 있다. $0 \le C_i \le 1\ 000\ 000\ 000$ ($1 \le i \le N$). $0 \le D_i \le 1\ 000\ 000\ 000$ ($1 \le i \le N$). $1 \le A_i \le B_i \le N-1$ ($1 \le i \le N$). $1 \le Q \le N$. $1 \le E_j \le N$ ($1 \le j \le Q$).