특별관광도시

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$번 도시 중에서 $x$번 도시에 가까운 도시는 $a$번 도시이고, 먼 도시는 $b$번 도시라고 하자. 여기서, 가까운 도시라고 함은 $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$ 번째 계획에서 이사장의 개인 자금에서 나가는 도로 정비 비용의 최솟값이어야 한다.

• $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$).