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 <class T>
void print(T& x) {
  cout << x;
}
template <class T, class U>
void print(pair<T, U>& p) {
  cout << "(";
  print(p.first);
  cout << ", ";
  print(p.second);
  cout << ")";
}
template <class T>
void print(vector<T>& v) {
  cout << "{";
  if (((int)(v).size())) print(v[0]);
  for (int i = 1; i < ((int)(v).size()); i++) cout << ", ", print(v[i]);
  cout << "}\n";
}
template <class T>
void print(deque<T>& v) {
  cout << "{";
  if (((int)(v).size())) print(v[0]);
  for (int i = 1; i < ((int)(v).size()); i++) cout << ", ", print(v[i]);
  cout << "}\n";
}
int N, Q;
vector<vector<int>> G;
vector<vector<pair<int, int>>> T;
vector<int> num, fromNum, depth, l, r;
int C;
struct sparse_table {
  int n;
  vector<int> a;
  vector<vector<int>> st;
  int combine(int dl, int dr) { return a[dl] > a[dr] ? dl : dr; }
  sparse_table() {}
  sparse_table(vector<int>& a)
      : n(((int)(a).size())),
        a(a),
        st((31 - __builtin_clz(n)) + 1, vector<int>(n)) {
    for (int i = 0; i < n; i++) st[0][i] = i;
    for (int j = 1; 1 << j <= n; j++)
      for (int i = 0; i + (1 << j) <= n; i++)
        st[j][i] = combine(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
  }
  int query(int l, int r) {
    int s = (31 - __builtin_clz(r - l));
    return combine(st[s][l], st[s][r - (1 << s)]);
  }
};
struct lowest_common_ancestor {
  int n, m = 0;
  vector<int> a, v, h;
  vector<vector<int>>& e;
  sparse_table st;
  lowest_common_ancestor(vector<vector<int>>& e, int r)
      : n(((int)(e).size())), a(n), v(2 * n - 1), h(2 * n - 1), e(e) {
    dfs(r);
    st = sparse_table(h);
  }
  void dfs(int i, int p = -1, int d = 0) {
    a[i] = m;
    v[m] = i;
    h[m++] = d;
    for (int j : e[i]) {
      if (j == p) continue;
      dfs(j, i, d - 1);
      v[m] = i;
      h[m++] = d;
    }
  }
  int lca(int x, int y) {
    return v[st.query(min(a[x], a[y]), max(a[x], a[y]) + 1)];
  }
};
void dfs(int cur, int par) {
  num[cur] = C++;
  l[num[cur]] = num[cur];
  fromNum[num[cur]] = cur;
  for (int x : G[cur]) {
    if (x != par) {
      depth[x] = depth[cur] + 1;
      dfs(x, cur);
    }
  }
  r[num[cur]] = C - 1;
}
void build(deque<int>& res) {
  int cur = res[0];
  res.pop_front();
  while (((int)(res).size()) && res[0] >= l[cur] && res[0] <= r[cur]) {
    T[cur].push_back({res[0], depth[fromNum[res[0]]] - depth[fromNum[cur]]});
    T[res[0]].push_back({cur, depth[fromNum[res[0]]] - depth[fromNum[cur]]});
    build(res);
  }
}
deque<int> buildTree(vector<int>& cur, lowest_common_ancestor& lca) {
  deque<int> res(cur.begin(), cur.end());
  for (int i = 0; i < ((int)(cur).size()) - 1; i++) {
    res.push_back(num[lca.lca(fromNum[cur[i]], fromNum[cur[i + 1]])]);
  }
  sort(res.begin(), res.end());
  res.erase(unique(res.begin(), res.end()), res.end());
  return res;
}
void buildTree2(deque<int> res) { build(res); }
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> N;
  G.resize(N);
  num.resize(N);
  fromNum.resize(N);
  l.resize(N);
  r.resize(N);
  depth.resize(N);
  T.resize(N);
  for (int i = 0; i < N - 1; i++) {
    int u, v;
    cin >> u >> v;
    u--;
    v--;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  dfs(0, -1);
  lowest_common_ancestor lca(G, 0);
  cin >> Q;
  vector<char> vis(N);
  vector<int> vir(N);
  while (Q--) {
    int k, m;
    cin >> k >> m;
    vector<int> cur, v(k), s(k), imp(m);
    priority_queue<tuple<int, int, int, int>, vector<tuple<int, int, int, int>>,
                   greater<tuple<int, int, int, int>>>
        PQ;
    for (int i = 0; i < k; i++) {
      cin >> v[i] >> s[i];
      v[i]--;
      cur.push_back(num[v[i]]);
      PQ.push({0, i, num[v[i]], 0});
    }
    for (int i = 0; i < m; i++) {
      cin >> imp[i];
      imp[i]--;
      cur.push_back(num[imp[i]]);
    }
    sort(cur.begin(), cur.end());
    cur.erase(unique(cur.begin(), cur.end()), cur.end());
    deque<int> allV = buildTree(cur, lca);
    buildTree2(allV);
    for (int x : allV) vis[x] = false;
    while (!PQ.empty()) {
      auto [dist, ind, cur, totStep] = PQ.top();
      PQ.pop();
      if (vis[cur]) continue;
      vis[cur] = true;
      vir[cur] = ind;
      for (auto [x, d] : T[cur]) {
        if (!vis[x]) {
          int newDist = (totStep + d + s[ind] - 1) / s[ind];
          int newTot = totStep + d;
          PQ.push({newDist, ind, x, newTot});
        }
      }
    }
    for (int x : imp) {
      cout << vir[num[x]] + 1 << " ";
    }
    cout << "\n";
    for (int x : allV) T[x].clear();
  }
}