Problem: 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.

Input

The first line contains a single integer n (1 ≤ n ≤ 2 ⋅ 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 ≤ x_i, y_i ≤ 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 ≤ q ≤ 2 ⋅ 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 ≤ k_i, m_i ≤ n) — the number of virus species and the number of important cities in this scenario respectively. It is guaranteed that ∑_{i = 1}^ q k_i and ∑_{i = 1}^ q m_i do not exceed 2 ⋅ 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 ≤ v_j ≤ n, 1 ≤ s_j ≤ 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, …, u_{m_i} (1 ≤ u_j ≤ 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, …, 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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int f = 1, ans = 0;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    ans = ans * 10 + c - '0';
    c = getchar();
  }
  return f * ans;
}
const int MAXN = 4e5 + 11;
vector<int> vec[MAXN], C;
int N, dfn[MAXN], dep[MAXN], Q, A[MAXN], R[MAXN], B[MAXN], Que[MAXN],
    fa[MAXN][21], sta[MAXN], vis[MAXN];
void dfs(int u, int fath) {
  dep[u] = dep[fath] + 1;
  dfn[u] = ++dfn[0];
  fa[u][0] = fath;
  for (int i = 1; (1 << i) <= dep[u]; i++) fa[u][i] = fa[fa[u][i - 1]][i - 1];
  for (auto v : vec[u])
    if (v != fath) dfs(v, u);
  return;
}
int Qlca(int u, int v) {
  if (dep[u] < dep[v]) swap(u, v);
  for (int i = 20; i >= 0; i--)
    if (dep[u] - (1 << i) >= dep[v]) u = fa[u][i];
  if (u == v) return u;
  for (int i = 20; i >= 0; i--)
    if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
  return fa[u][0];
}
bool cmp(int x, int y) { return dfn[x] < dfn[y]; }
int ca, cb, str[MAXN];
void ins(int x) {
  if (sta[0] == 1) {
    sta[++sta[0]] = x;
    return;
  }
  int now = Qlca(sta[sta[0]], x);
  while (sta[0] > 1 && dep[sta[sta[0] - 1]] >= dep[now])
    vec[sta[sta[0] - 1]].push_back(sta[sta[0]]),
        vec[sta[sta[0]]].push_back(sta[sta[0] - 1]), sta[0]--;
  if (dep[sta[sta[0]]] > dep[now])
    vec[now].push_back(sta[sta[0]]), vec[sta[sta[0]]].push_back(now), sta[0]--;
  if (sta[sta[0]] != now) sta[++sta[0]] = now;
  sta[++sta[0]] = x;
  return;
}
void build() {
  sta[0] = 0;
  Que[++Que[0]] = 1;
  sort(Que + 1, Que + Que[0] + 1, cmp);
  sta[++sta[0]] = 1;
  for (int i = 2; i <= Que[0]; i++)
    if (Que[i] != Que[i - 1]) ins(Que[i]);
  while (sta[0] > 1)
    vec[sta[sta[0] - 1]].push_back(sta[sta[0]]),
        vec[sta[sta[0]]].push_back(sta[sta[0] - 1]), sta[0]--;
  return;
}
void dfs1(int u, int fath) {
  C.push_back(u);
  for (auto v : vec[u])
    if (v != fath) dfs1(v, u);
}
void clear() {
  for (auto v : C) vec[v].clear();
}
struct node {
  int dis, id, pre, tim;
  bool operator<(const node a) const {
    return a.tim == tim ? a.pre < pre : a.tim < tim;
  }
} tr[MAXN];
int Get(int dis, int pre) { return (dis - 1) / R[pre] + 1; }
priority_queue<node> que;
void dijkstra() {
  while (!que.empty()) que.pop();
  C.clear();
  dfs1(1, 0);
  for (auto x : C)
    tr[x].dis = N + 1, tr[x].id = x, tr[x].pre = 0, tr[x].tim = N + 1,
    vis[x] = 0;
  for (int x = 1; x <= ca; x++)
    tr[A[x]].dis = 0, tr[A[x]].pre = x, tr[A[x]].tim = 0, que.push(tr[A[x]]);
  while (!que.empty()) {
    int u = que.top().id;
    que.pop();
    if (vis[u]) continue;
    vis[u] = 1;
    for (auto v : vec[u]) {
      node o;
      o.dis = tr[u].dis + abs(dep[u] - dep[v]), o.id = v, o.pre = tr[u].pre,
      o.tim = Get(o.dis, o.pre);
      if (!(o < tr[v])) tr[v] = o, que.push(tr[v]);
    }
  }
  return;
}
int main() {
  N = read();
  for (int i = 1; i < N; i++) {
    int u = read(), v = read();
    vec[u].push_back(v), vec[v].push_back(u);
  }
  dfs(1, 0);
  for (int i = 1; i <= N; i++) vec[i].clear();
  Q = read();
  while (Q--) {
    ca = read(), cb = read();
    Que[0] = 0;
    for (int i = 1; i <= ca; i++) A[i] = Que[++Que[0]] = read(), R[i] = read();
    for (int i = 1; i <= cb; i++) B[i] = Que[++Que[0]] = read();
    build();
    dijkstra();
    for (int i = 1; i <= cb; i++) printf("%d ", tr[B[i]].pre);
    printf("\n");
    clear();
  }
}