Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Treeland and Viruses

time limit per test

3 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputThere 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.

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.

Example

Input

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

Output

1 2 1 1 1 1 1

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/19/2021 10:32:51 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|