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>
const int inf = 0x3f3f3f3f, Inf = 0x7fffffff;
const long long INF = 0x7fffffffffffffff;
const double eps = 1e-10;
unsigned int seed = 19260817;
const unsigned int _RAND_MAX_ = 4294967295u;
__inline__ __attribute__((always_inline)) unsigned int Rand() {
  return seed = seed * 998244353u + 1000000007u;
}
template <typename _Tp>
_Tp gcd(const _Tp &a, const _Tp &b) {
  return (!b) ? a : gcd(b, a % b);
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) _Tp abs(const _Tp &a) {
  return a >= 0 ? a : -a;
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) _Tp max(const _Tp &a, const _Tp &b) {
  return a < b ? b : a;
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) _Tp min(const _Tp &a, const _Tp &b) {
  return a < b ? a : b;
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) void chmax(_Tp &a, const _Tp &b) {
  (a < b) && (a = b);
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) void chmin(_Tp &a, const _Tp &b) {
  (b < a) && (a = b);
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) bool _cmp(const _Tp &a,
                                                    const _Tp &b) {
  return abs(a - b) <= eps;
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) void read(_Tp &x) {
  register char ch(getchar());
  bool f(false);
  while (ch < 48 || ch > 57) f |= ch == 45, ch = getchar();
  x = ch & 15, ch = getchar();
  while (ch >= 48 && ch <= 57)
    x = (((x << 2) + x) << 1) + (ch & 15), ch = getchar();
  if (f) x = -x;
}
template <typename _Tp, typename... Args>
__inline__ __attribute__((always_inline)) void read(_Tp &t, Args &...args) {
  read(t);
  read(args...);
}
__inline__ __attribute__((always_inline)) int read_str(char *s) {
  register char ch(getchar());
  while (ch == ' ' || ch == '\r' || ch == '\n') ch = getchar();
  register char *tar = s;
  *tar = ch, ch = getchar();
  while (ch != ' ' && ch != '\r' && ch != '\n' && ch != EOF)
    *(++tar) = ch, ch = getchar();
  return tar - s + 1;
}
const int N = 200005;
struct edge {
  int v, nxt;
} c[N << 1];
int front[N], cnt;
__inline__ __attribute__((always_inline)) void add(int u, int v) {
  c[++cnt] = (edge){v, front[u]}, front[u] = cnt;
}
struct Edge {
  int v, w;
};
std::vector<Edge> v[N];
__inline__ __attribute__((always_inline)) void add(int u, int x, int w) {
  v[u].push_back((Edge){x, w});
  v[x].push_back((Edge){u, w});
}
int dep[N], son[N], siz[N], Fa[N];
int dfn[N], id, Top[N];
void dfs1(int x, int fa) {
  dep[x] = dep[fa] + 1;
  Fa[x] = fa, siz[x] = 1;
  for (int i = front[x]; i; i = c[i].nxt) {
    if (c[i].v != fa) {
      dfs1(c[i].v, x);
      siz[x] += siz[c[i].v];
      if (siz[c[i].v] > siz[son[x]]) {
        son[x] = c[i].v;
      }
    }
  }
}
void dfs2(int x, int topf) {
  Top[x] = topf;
  dfn[x] = ++id;
  if (!son[x]) return;
  dfs2(son[x], topf);
  for (int i = front[x]; i; i = c[i].nxt) {
    if (!Top[c[i].v]) {
      dfs2(c[i].v, c[i].v);
    }
  }
}
int lca(int x, int y) {
  while (Top[x] != Top[y]) {
    if (dep[Top[x]] > dep[Top[y]])
      x = Fa[Top[x]];
    else
      y = Fa[Top[y]];
  }
  return dep[x] < dep[y] ? x : y;
}
struct node {
  int u;
  int a, b, id;
  __inline__ __attribute__((always_inline)) bool operator<(
      const node &o) const {
    return a == o.a ? id > o.id : a > o.a;
  }
};
int s[N];
std::priority_queue<node> q;
int st[N], top;
int t[N << 1], pos;
int last;
void insert(int x) {
  if (x == last) return;
  last = x;
  if (!top ||
      (dfn[x] >= dfn[st[top]] && dfn[x] < dfn[st[top]] + siz[st[top]])) {
    st[++top] = x;
    t[++pos] = x;
    return;
  }
  int l = lca(x, st[top]);
  while (top > 1 && dfn[st[top - 1]] >= dfn[l]) {
    add(st[top - 1], st[top], dep[st[top]] - dep[st[top - 1]]);
    --top;
  }
  if (st[top] != l) {
    add(l, st[top], dep[st[top]] - dep[l]);
    st[top] = l;
    t[++pos] = l;
  }
  st[++top] = x;
  t[++pos] = x;
}
struct Node {
  int dis, id;
  __inline__ __attribute__((always_inline)) bool operator<(
      const Node &o) const {
    return dis == o.dis ? id < o.id : dis < o.dis;
  }
} dis[N];
int ans[N];
int p[N];
bool mark[N];
void dij() {
  while (!q.empty()) {
    node x = q.top();
    q.pop();
    if (ans[x.u]) {
      if (!mark[x.u]) continue;
      if (x.id == ans[x.u]) {
        mark[x.u] = false;
      } else
        continue;
    }
    ans[x.u] = x.id;
    for (auto it : v[x.u]) {
      int qwq = (x.a * s[x.id] + x.b + it.w) / s[x.id];
      int qaq = (x.a * s[x.id] + x.b + it.w) % s[x.id];
      if (!qaq) {
        qaq = s[x.id];
        --qwq;
      }
      if ((Node){qwq, x.id} < dis[it.v]) {
        dis[it.v] = (Node){qwq, x.id};
        q.push((node){it.v, qwq, qaq, x.id});
      }
    }
  }
}
int nd[N << 1], len;
int main() {
  int n;
  read(n);
  int x, y;
  for (int i = 1; i < n; ++i) {
    read(x, y);
    add(x, y), add(y, x);
  }
  for (int i = 1; i <= n; ++i) dis[i] = (Node){inf, inf};
  dfs1(1, 0);
  dfs2(1, 1);
  int _;
  read(_);
  while (_--) {
    last = 0;
    while (!q.empty()) q.pop();
    len = 0;
    int k, m;
    read(k, m);
    for (int i = 1; i <= k; ++i) {
      read(x, s[i]);
      nd[++len] = x;
      q.push((node){x, 0, 0, i});
      ans[x] = i;
      mark[x] = true;
      dis[x] = (Node){0, i};
    }
    for (int i = 1; i <= m; ++i) {
      read(x);
      nd[++len] = x;
      p[i] = x;
    }
    std::sort(nd + 1, nd + len + 1,
              [](int a, int b) -> bool { return dfn[a] < dfn[b]; });
    for (int i = 1; i <= len; ++i) insert(nd[i]);
    while (top > 1)
      add(st[top - 1], st[top], dep[st[top]] - dep[st[top - 1]]), --top;
    top = 0;
    dij();
    for (int i = 1; i <= m; ++i) printf("%d ", ans[p[i]]);
    printf("\n");
    while (pos) {
      mark[t[pos]] = 0;
      ans[t[pos]] = 0;
      dis[t[pos]] = (Node){inf, inf};
      v[t[pos--]].clear();
    }
  }
  return 0;
}