Given a tree graph with $N$ vertices and $Q$ queries.
The $i$-th query consists of $m_i$ special vertices $x_1,x_2,x_3,\dots x_{m_i}$.
A vertex $u$ on the tree is considered to be occupied by a special vertex $x$ if the distance from $u$ to $x$ is the smallest among the $m_i$ special vertices (if the distance from $u$ to $x_1$ is equal to the distance from $u$ to $x_2$ and $x_1 < x_2$, then $u$ will preferentially be occupied by $x_1$).
For each query, print the number of vertices that each special vertex $x_i$ occupies.
### Input
- The first line contains an integer $N$.
- The next $N-1$ lines describe the edges of the tree.
- The following line contains an integer $Q$.
- The next $Q \times 2$ lines are structured as follows:
- The first line contains an integer $m_i$.
- The next line contains $m_i$ integers $x_1, x_2, \ldots$, which are the special vertices.
### Output
- Output the answer for each query in the order of the input.
### Constraints
- $N, Q \le 500000$.
- $m_i, x_i \le n$.
- $\sum_{i=1}^{Q} m_i$ $\le 500000$
### Example
Input:
```
10
2 1
3 2
4 3
5 4
6 1
7 3
8 3
9 4
10 1
1
4
8 7 10 3
```
Output:
```
1 1 3 5
```