The kingdom of Byteland has 𝑛 cities connected by $n - 1$ two-way roads. It can be described as follows: the $i$-th road connects two cities $a_i$ and $b_i$ with 2 lanes: one lane goes from $a_i$ to $b_i$, and the other lane goes from $b_i$ to $a_i$. The roads ensure traffic between the cities. This year, the kingdom is plagued by an epidemic. After a period of nationwide lockdown, the king wants to choose $k$ cities as "green zones" for normal activities to restore the economy. Additionally, all households **on the shortest path from any city to a city in the green zone** will also be allowed to operate normally to provide transportation services. On a road, the number of households on the two lanes is different: for a road $i$, the number of households on the lane from $a_i$ to $b_i$ is $c_i$, and the number of households on the lane from $b_i$ to $a_i$ is $d_i$. To meet the wishes of the majority of the population, the king wants to choose 𝑘 cities as green zones so that the number of households allowed to operate is maximized.
Requirements: You need to answer $Q$ questions, each question asking for the number of cities $k$. You need to find the solution of choosing $k$ cities as green zones so that, with the chosen solution, the maximum number of households is allowed to operate. Provide the number of households.
### Input
- The first line is a positive integer $n (1 \le n \le 10^5)$, the number of cities in the kingdom.
- The next $n - 1$ lines each contain 4 numbers $a_i, b_i, c_i, d_i (1 \le c_i, d_i \le 10^9)$.
- The next line contains a positive integer $Q (Q \le 10^5)$, the number of questions from the king.
- The next $Q$ lines each contain a positive integer $k$ corresponding to a question $(1 \le k \le n)$.
### Output
- Output $Q$ lines, each line is the maximum number of households allowed to operate for the chosen solution corresponding to a question.
### Constraints
- 20% of tests have $n \le 16$.
- 20% of tests have $Q=1, k=1$.
- 30% of tests have $n \le 2000$.
- 30% of tests have no additional constraints.
### Example
Input:
```
5
2 1 1 2
2 3 1 2
2 4 1 2
2 5 2 1
2
1 2
```
Output:
```
8
10
```
**Explanation:**
- $k=1$: Choose city $5$.
- $k=2$: Choose cities $1$ and $5`.
