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;
template <typename T>
inline void read(T &x) {
  x = 0;
  char c = getchar();
  bool flag = false;
  while (!isdigit(c)) {
    if (c == '-') flag = true;
    c = getchar();
  }
  while (isdigit(c)) {
    x = (x << 1) + (x << 3) + (c ^ 48);
    c = getchar();
  }
  if (flag) x = -x;
}
int n, m, k, t, cnt, top, tot;
int in[800010], out[800010], tp[800010], f[800010], son[800010], dep[800010],
    siz[800010];
int q[800010], st[800010], fa[800010], col[800010], bel[800010], s[800010],
    sp[800010];
struct edge {
  int to, nxt;
} e[800010];
int head[800010], edge_cnt;
void add(int from, int to) {
  e[++edge_cnt] = {to, head[from]}, head[from] = edge_cnt;
}
bool cmp(const int &a, const int &b) { return in[a] < in[b]; }
void dfs_son(int x, int fath) {
  siz[x] = 1, f[x] = fath, dep[x] = dep[fath] + 1;
  for (int i = head[x]; i; i = e[i].nxt) {
    int y = e[i].to;
    if (y == fath) continue;
    dfs_son(y, x), siz[x] += siz[y];
    if (siz[son[x]] < siz[y]) son[x] = y;
  }
}
void dfs_chain(int x, int t) {
  in[x] = ++cnt, tp[x] = t;
  if (son[x]) dfs_chain(son[x], t);
  for (int i = head[x]; i; i = e[i].nxt) {
    int y = e[i].to;
    if (in[y]) continue;
    dfs_chain(y, y);
  }
  out[x] = cnt;
}
int lca(int x, int y) {
  while (tp[x] != tp[y]) {
    if (dep[tp[x]] < dep[tp[y]]) swap(x, y);
    x = f[tp[x]];
  }
  if (in[x] > in[y]) swap(x, y);
  return x;
}
int dis(int x, int y) { return dep[x] + dep[y] - dep[lca(x, y)] * 2; }
int calc(int x, int y) { return (dis(x, y) + sp[col[x]] - 1) / sp[col[x]]; }
void build() {
  sort(s + 1, s + tot + 1, cmp);
  for (int i = tot - 1; i; --i) s[++tot] = lca(s[i], s[i + 1]);
  sort(s + 1, s + tot + 1, cmp), tot = unique(s + 1, s + tot + 1) - s - 1,
                                 top = 0;
  for (int i = 1; i <= tot; ++i) {
    while (top && out[st[top]] < in[s[i]]) top--;
    if (top) fa[s[i]] = st[top];
    st[++top] = s[i];
  }
}
int get(int x, int a, int b) {
  if (!x) return 0;
  if (!a || !b) return a + b;
  int da = calc(a, x), db = calc(b, x);
  if (da == db) return col[a] < col[b] ? a : b;
  return da < db ? a : b;
}
void clear() {
  for (int i = 1; i <= tot; ++i) fa[s[i]] = bel[s[i]] = 0;
  tot = 0;
}
int main() {
  read(n);
  for (int i = 1; i < n; ++i) {
    int x, y;
    read(x), read(y);
    add(x, y), add(y, x);
  }
  dfs_son(1, 0), dfs_chain(1, 1);
  read(m);
  while (m--) {
    read(k), read(t);
    for (int i = 1; i <= k; ++i) {
      int x;
      read(x), read(sp[i]);
      col[x] = i, bel[x] = x, s[++tot] = x;
    }
    for (int i = 1; i <= t; ++i) {
      int x;
      read(x), s[++tot] = x, q[i] = x;
    }
    build();
    for (int i = tot; i; --i)
      bel[fa[s[i]]] = get(fa[s[i]], bel[fa[s[i]]], bel[s[i]]);
    for (int i = 1; i <= tot; ++i)
      bel[s[i]] = get(s[i], bel[fa[s[i]]], bel[s[i]]);
    for (int i = 1; i <= t; ++i) printf("%d%c", col[bel[q[i]]], " \n"[i == t]);
    clear();
  }
  return 0;
}