Treeland and Viruses
Description
There are $n$ cities in Treeland connected with $n - 1$ bidirectional roads in such that a way that any city is reachable from any other; in other words, the graph of cities and roads is a tree. Treeland is preparing for a seasonal virus epidemic, and currently, they are trying to evaluate different infection scenarios.
In each scenario, several cities are initially infected with different virus species. Suppose that there are $k_i$ virus species in the $i$-th scenario. Let us denote $v_j$ the initial city for the virus $j$, and $s_j$ the propagation speed of the virus $j$. The spread of the viruses happens in turns: first virus $1$ spreads, followed by virus $2$, and so on. After virus $k_i$ spreads, the process starts again from virus $1$.
A spread turn of virus $j$ proceeds as follows. For each city $x$ not infected with any virus at the start of the turn, at the end of the turn it becomes infected with virus $j$ if and only if there is such a city $y$ that:
- city $y$ was infected with virus $j$ at the start of the turn;
- the path between cities $x$ and $y$ contains at most $s_j$ edges;
- all cities on the path between cities $x$ and $y$ (excluding $y$) were uninfected with any virus at the start of the turn.
Once a city is infected with a virus, it stays infected indefinitely and can not be infected with any other virus. The spread stops once all cities are infected.
You need to process $q$ independent scenarios. Each scenario is described by $k_i$ virus species and $m_i$ important cities. For each important city determine which the virus it will be infected by in the end.
The first line contains a single integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the number of cities in Treeland.
The following $n - 1$ lines describe the roads. The $i$-th of these lines contains two integers $x_i$ and $y_i$ ($1 \leq x_i, y_i \leq n$) — indices of cities connecting by the $i$-th road. It is guaranteed that the given graph of cities and roads is a tree.
The next line contains a single integer $q$ ($1 \leq q \leq 2 \cdot 10^5$) — the number of infection scenarios. $q$ scenario descriptions follow.
The description of the $i$-th scenario starts with a line containing two integers $k_i$ and $m_i$ ($1 \leq k_i, m_i \leq n$) — the number of virus species and the number of important cities in this scenario respectively. It is guaranteed that $\sum_{i = 1}^ q k_i$ and $\sum_{i = 1}^ q m_i$ do not exceed $2 \cdot 10^5$.
The following $k_i$ lines describe the virus species. The $j$-th of these lines contains two integers $v_j$ and $s_j$ ($1 \leq v_j \leq n$, $1 \leq s_j \leq 10^6$) – the initial city and the propagation speed of the virus species $j$. It is guaranteed that the initial cities of all virus species within a scenario are distinct.
The following line contains $m_i$ distinct integers $u_1, \ldots, u_{m_i}$ ($1 \leq u_j \leq n$) — indices of important cities.
Print $q$ lines. The $i$-th line should contain $m_i$ integers — indices of virus species that cities $u_1, \ldots, u_{m_i}$ are infected with at the end of the $i$-th scenario.
Input
The first line contains a single integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the number of cities in Treeland.
The following $n - 1$ lines describe the roads. The $i$-th of these lines contains two integers $x_i$ and $y_i$ ($1 \leq x_i, y_i \leq n$) — indices of cities connecting by the $i$-th road. It is guaranteed that the given graph of cities and roads is a tree.
The next line contains a single integer $q$ ($1 \leq q \leq 2 \cdot 10^5$) — the number of infection scenarios. $q$ scenario descriptions follow.
The description of the $i$-th scenario starts with a line containing two integers $k_i$ and $m_i$ ($1 \leq k_i, m_i \leq n$) — the number of virus species and the number of important cities in this scenario respectively. It is guaranteed that $\sum_{i = 1}^ q k_i$ and $\sum_{i = 1}^ q m_i$ do not exceed $2 \cdot 10^5$.
The following $k_i$ lines describe the virus species. The $j$-th of these lines contains two integers $v_j$ and $s_j$ ($1 \leq v_j \leq n$, $1 \leq s_j \leq 10^6$) – the initial city and the propagation speed of the virus species $j$. It is guaranteed that the initial cities of all virus species within a scenario are distinct.
The following line contains $m_i$ distinct integers $u_1, \ldots, u_{m_i}$ ($1 \leq u_j \leq n$) — indices of important cities.
Output
Print $q$ lines. The $i$-th line should contain $m_i$ integers — indices of virus species that cities $u_1, \ldots, u_{m_i}$ are infected with at the end of the $i$-th scenario.
Samples
7
1 2
1 3
2 4
2 5
3 6
3 7
3
2 2
4 1
7 1
1 3
2 2
4 3
7 1
1 3
3 3
1 1
4 100
7 100
1 2 3
1 2
1 1
1 1 1