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>
template <class T>
inline void read(T &res) {
  res = 0;
  bool bo = 0;
  char c;
  while (((c = getchar()) < '0' || c > '9') && c != '-')
    ;
  if (c == '-')
    bo = 1;
  else
    res = c - 48;
  while ((c = getchar()) >= '0' && c <= '9')
    res = (res << 3) + (res << 1) + (c - 48);
  if (bo) res = ~res + 1;
}
template <class T>
inline T Min(const T &a, const T &b) {
  return a < b ? a : b;
}
const int N = 2e5 + 5, E = 20, M = N << 1;
const long long INF = 1e18;
int n, q, ecnt, nxt[M], adj[N], go[M], dfn[N], ToT, fa[N][E], dep[N], vn,
    vir[M], rt, top, par[N], stk[N], ecnt2, nxt2[M], adj2[N], go2[M], k, a[N],
    s[N], m, b[N], id[N];
bool vis[N], mark[N];
struct elem {
  long long t;
  int d;
  friend inline bool operator<(elem a, elem b) { return a.t < b.t; }
} f[N], g[N];
void add_edge(int u, int v) {
  nxt[++ecnt] = adj[u];
  adj[u] = ecnt;
  go[ecnt] = v;
  nxt[++ecnt] = adj[v];
  adj[v] = ecnt;
  go[ecnt] = u;
}
void add_edge2(int u, int v) {
  nxt2[++ecnt2] = adj2[u];
  adj2[u] = ecnt2;
  go2[ecnt2] = v;
  nxt2[++ecnt2] = adj2[v];
  adj2[v] = ecnt2;
  go2[ecnt2] = u;
}
void dfs(int u, int fu) {
  dfn[u] = ++ToT;
  dep[u] = dep[fa[u][0] = fu] + 1;
  for (int i = 0; i < 18; i++) fa[u][i + 1] = fa[fa[u][i]][i];
  for (int e = adj[u], v; e; e = nxt[e])
    if ((v = go[e]) != fu) dfs(v, u);
}
inline bool comp(int a, int b) { return dfn[a] < dfn[b]; }
int lca(int u, int v) {
  if (dep[u] < dep[v]) std::swap(u, v);
  for (int i = 18; i >= 0; i--)
    if (dep[fa[u][i]] >= dep[v]) u = fa[u][i];
  if (u == v) return u;
  for (int i = 18; i >= 0; i--)
    if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
  return fa[u][0];
}
void build() {
  std::sort(vir + 1, vir + vn + 1, comp);
  vn = std::unique(vir + 1, vir + vn + 1) - vir - 1;
  top = 0;
  for (int i = 1, tn = vn; i <= tn; i++) {
    int u = vir[i];
    if (!top) {
      par[stk[++top] = u] = 0;
      continue;
    }
    int w = lca(u, stk[top]);
    while (dep[stk[top]] > dep[w]) {
      if (dep[stk[top - 1]] < dep[w]) par[stk[top]] = w;
      top--;
    }
    if (stk[top] != w) par[w] = stk[top], stk[++top] = w, vir[++vn] = w;
    par[u] = w;
    stk[++top] = u;
  }
  ecnt2 = 0;
  for (int i = 1; i <= vn; i++) adj2[vir[i]] = 0;
  for (int i = 1; i <= vn; i++)
    if (par[vir[i]])
      add_edge2(par[vir[i]], vir[i]);
    else
      rt = vir[i];
}
elem trav(elem f, int w) {
  int x = s[(f.t - 1) % k + 1];
  if (f.d >= w)
    return (elem){f.t, f.d - w};
  else
    return (elem){f.t + 1ll * ((w - f.d + x - 1) / x) * k,
                  (f.d - w % x + x) % x};
}
void dfs1(int u, int fu) {
  f[u] = (elem){id[u] ? id[u] : INF, 0};
  for (int e = adj2[u], v; e; e = nxt2[e])
    if ((v = go2[e]) != fu)
      dfs1(v, u), f[u] = Min(f[u], trav(f[v], abs(dep[v] - dep[u])));
}
void dfs2(int u, int fu) {
  elem f1 = (elem){INF, 0}, f2 = (elem){INF, 0};
  for (int e = adj2[u], v; e; e = nxt2[e])
    if ((v = go2[e]) != fu) {
      elem fi = trav(f[v], abs(dep[v] - dep[u]));
      if (fi < f1)
        f2 = f1, f1 = fi;
      else if (fi < f2)
        f2 = fi;
    }
  if (fu) {
    elem fi = trav(g[u], abs(dep[u] - dep[fu]));
    if (fi < f1)
      f2 = f1, f1 = fi;
    else if (fi < f2)
      f2 = fi;
  }
  for (int e = adj2[u], v; e; e = nxt2[e]) {
    if ((v = go2[e]) == fu) continue;
    if (id[u])
      g[v] = (elem){id[u], 0};
    else
      g[v] = trav(f[v], abs(dep[v] - dep[u])).t == f1.t ? f2 : f1;
    dfs2(v, u);
  }
}
int main() {
  int x, y;
  read(n);
  for (int i = 1; i < n; i++) read(x), read(y), add_edge(x, y);
  dfs(1, 0);
  read(q);
  while (q--) {
    read(k);
    read(m);
    vn = 0;
    for (int i = 1; i <= k; i++) read(a[i]), read(s[i]), vir[++vn] = a[i];
    for (int i = 1; i <= m; i++) read(b[i]), vir[++vn] = b[i];
    build();
    for (int i = 1; i <= vn; i++) id[vir[i]] = 0;
    for (int i = 1; i <= k; i++) id[a[i]] = i;
    dfs1(rt, 0);
    g[rt] = (elem){INF, 0};
    dfs2(rt, 0);
    for (int i = 1; i <= m; i++)
      x = b[i],
      printf("%d ",
             (Min(trav(g[x], abs(dep[par[x]] - dep[x])), f[x]).t - 1) % k + 1);
    puts("");
  }
  return 0;
}