In a war, the battlefield consists of $n$ islands and $n-1$ bridges, such that there is exactly one path between any two islands. The enemy headquarters is located on island $1$, and they are running low on energy to sustain their operations. There are $k$ other islands that contain abundant energy resources. To prevent the enemy from obtaining these resources, our army must destroy some bridges so that the enemy cannot reach any of the energy-rich islands from island $1$. Since different bridges have different materials and structures, destroying them incurs different costs. We want to minimize the total cost while achieving our objective.

The intelligence department has discovered that the enemy possesses a mysterious machine. Even after we cut off all energy sources, they can use this machine. The machine not only repairs all the bridges we destroyed but also redistributes the resources randomly (it is guaranteed that resources will not be distributed to island $1$). However, the intelligence department also found that this machine can only be used $m$ times, so we only need to complete each task as it arises.

Input

The first line contains an integer $n$, representing the number of islands.

The next $n-1$ lines each contain three integers $u, v, w$, representing that island $u$ and island $v$ are directly connected by a bridge with a cost of $w$. It is guaranteed that $1 \le u, v \le n$ and $1 \le w \le 100\,000$.

The $(n+1)$-th line contains an integer $m$, representing the number of times the enemy machine can be used.

The next $m$ lines each contain an integer $k_i$, representing that after the $i$-th use of the machine, there are $k_i$ islands with abundant resources, followed by $k_i$ integers $h_1, h_2, \dots, h_{k_i}$, representing the indices of the resource-rich islands.

Output

Output $m$ lines, each representing the minimum cost for each task.

Examples

Input 1

10
1 5 13
1 9 6
2 1 19
2 4 8
2 3 91
5 6 8
7 5 4
7 8 31
10 7 9
3
2 10 6
4 5 7 8 3
3 9 4 6

Output 1

12
32
22

Constraints

For $10\%$ of the data: $2 \le n \le 10, 1 \le m \le 5, 1 \le k_i \le n-1$

For $20\%$ of the data: $2 \le n \le 100, 1 \le m \le 100, 1 \le k_i \le \min(10, n-1)$

For $40\%$ of the data: $2 \le n \le 1000, m \ge 1, \sum k_i \le 500\,000, 1 \le k_i \le \min(15, n-1)$

For $100\%$ of the data: $2 \le n \le 250\,000, m \ge 1, \sum k_i \le 500\,000, 1 \le k_i \le n-1$