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 B = 2 << 20;
struct streambufcin {
  std::streambuf *in;
  streambufcin() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    in = std::cin.rdbuf();
    bg = ed = NULL;
  }
  char buf[B], *bg, *ed, ch;
  char gc() {
    return bg == ed ? ed = buf + in->sgetn(bg = buf, B),
                      (bg == ed ? -1 : *bg++) : *bg++;
  }
  template <class T>
  streambufcin &operator>>(T &x) {
    bool neg = false;
    for (ch = gc(); !isdigit(ch); ch = gc())
      ;
    if (ch == '-') neg = true;
    for (x = 0; isdigit(ch); ch = gc()) x = x * 10 + ch - 48;
    if (neg) x = -x;
    return *this;
  }
  streambufcin &operator>>(char &c) {
    for (c = gc(); isspace(c); c = gc())
      ;
    return *this;
  }
} cin;
struct streambufcout {
  std::streambuf *out = std::cout.rdbuf();
  char buf[B], *optr = buf;
  streambufcout() { out = std::cout.rdbuf(); }
  ~streambufcout() { flush(); }
  void flush() {
    out->sputn(buf, optr - buf);
    optr = buf;
  }
  void pc(char c) {
    if (optr == buf + B) flush();
    *optr++ = c;
  }
  template <class T>
  streambufcout &operator<<(T x) {
    static int st[233], top;
    if (x < 0) {
      x = -x;
      pc('-');
    }
    do {
      st[++top] = x % 10;
      x /= 10;
    } while (x);
    while (top) pc(st[top--] ^ 48);
    return *this;
  }
  streambufcout &operator<<(char c) {
    pc(c);
    return *this;
  }
} cout;
int n;
const int N = 200001;
const int K = 18;
struct edge {
  int v, nxt;
} e[N << 1];
int head[N], cnt;
void add(int u, int v) {
  e[++cnt] = {v, head[u]}, head[u] = cnt;
  e[++cnt] = {u, head[v]}, head[v] = cnt;
}
int par[N][K], dep[N], dfn[N], Index;
void dfs(int u, int father) {
  *par[u] = father;
  dep[u] = dep[father] + 1;
  dfn[u] = ++Index;
  for (int i = head[u]; i; i = e[i].nxt) {
    int v = e[i].v;
    if (v != father) dfs(v, u);
  }
}
int lca(int x, int y) {
  if (dep[x] < dep[y]) std::swap(x, y);
  for (int i = K - 1; ~i; --i)
    if (dep[par[x][i]] >= dep[y]) x = par[x][i];
  if (x == y) return x;
  for (int i = K - 1; ~i; --i)
    if (par[x][i] != par[y][i]) x = par[x][i], y = par[y][i];
  return par[x][0];
}
int getdis(int x, int y) { return dep[x] + dep[y] - 2 * dep[lca(x, y)]; }
struct Condition {
  int col, speed, di, time;
  bool operator<(const Condition &rhs) const {
    if (time != rhs.time) return time < rhs.time;
    if (col != rhs.col) return col < rhs.col;
    return di > rhs.di;
  }
} condition[N], initial;
int query[N];
struct Node {
  Condition p;
  int x;
  bool operator<(const Node &rhs) const { return rhs.p < p; }
};
int a[N * 2], tot;
bool cmp(int x, int y) { return dfn[x] < dfn[y]; }
std::vector<int> g[N];
void adde(int x, int y) {
  g[x].push_back(y);
  g[y].push_back(x);
}
int st[N * 2], top;
void insert(int x) {
  if (top == 1) {
    st[++top] = x;
    return;
  }
  int _lca = lca(x, st[top]);
  if (_lca == st[top]) {
    st[++top] = x;
    return;
  }
  while (top > 1 && dfn[st[top - 1]] >= dfn[_lca]) {
    adde(st[top], st[top - 1]);
    --top;
  }
  if (_lca != st[top]) {
    adde(st[top], _lca);
    st[top] = _lca;
  }
  st[++top] = x;
}
void build_tree() {
  std::sort(a + 1, a + tot + 1, cmp);
  st[top = 1] = a[0] = 1;
  for (int i = 1; i <= tot; i++) {
    if (a[i] == a[i - 1]) continue;
    insert(a[i]);
  }
  while (top > 0) {
    adde(st[top], st[top - 1]);
    --top;
  }
}
bool Cmp(Condition a, Node b) { return a < b.p; }
std::priority_queue<Node> q;
Condition To(int u, int v) {
  int dis = getdis(u, v);
  Condition now = condition[u];
  if (dis <= condition[u].di) {
    now.di -= dis;
    return now;
  }
  dis -= condition[u].di;
  int t = (dis - 1) / condition[u].speed + 1;
  now.di = t * condition[u].speed - dis;
  now.time += t;
  return now;
}
void dij() {
  while (!q.empty()) {
    Node u = q.top();
    q.pop();
    if (Cmp(condition[u.x], u)) continue;
    for (auto v : g[u.x]) {
      Condition nxt = To(u.x, v);
      if (nxt < condition[v]) {
        condition[v] = nxt;
        q.push({condition[v], v});
      }
    }
  }
}
void clear(int u, int father) {
  for (auto v : g[u]) {
    if (v != father) clear(v, u);
  }
  g[u].clear();
  condition[u] = initial;
}
void solve() {
  int m, k;
  cin >> m >> k;
  for (int i = 1; i <= m; i++) {
    int v;
    cin >> a[i] >> v;
    condition[a[i]].col = i;
    condition[a[i]].speed = v;
    condition[a[i]].time = 0;
    q.push({condition[a[i]], a[i]});
  }
  tot = m;
  for (int i = 1; i <= k; i++) {
    cin >> query[i];
    a[++tot] = query[i];
  }
  build_tree();
  dij();
  for (int i = 1; i <= k; i++) cout << condition[query[i]].col << ' ';
  cout << '\n';
  clear(1, 0);
}
int main() {
  cin >> n;
  for (int i = 1; i < n; i++) {
    int x, y;
    cin >> x >> y;
    add(x, y);
  }
  dfs(1, 0);
  for (int j = 1; j < K; j++)
    for (int i = 1; i <= n; i++) par[i][j] = par[par[i][j - 1]][j - 1];
  initial.col = n + 1;
  initial.time = n + 1;
  for (int i = 1; i <= n; i++) condition[i] = initial;
  int test;
  cin >> test;
  while (test--) solve();
  return 0;
}