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;
double PI = 3.141592653589793238462643383279;
const double EPS = 1e-9;
const long long MOD = 1000000007;
const int inf = 1 << 30;
const long long linf = 1LL << 60;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct LCA {
  vector<vector<int>> G;
  int root;
  int MAX_LOG_N;
  vector<vector<int>> parent;
  vector<int> depth;
  vector<int> order;
  void dfs(int v, int p, int d, int& tmp) {
    parent[0][v] = p;
    depth[v] = d;
    order[v] = tmp++;
    for (int i = 0; i < (int)G[v].size(); i++) {
      if (G[v][i] != p) dfs(G[v][i], v, d + 1, tmp);
    }
  }
  void init(int V, vector<vector<int>> _G, int root) {
    {
      int tmp = 1;
      MAX_LOG_N = 1;
      while (tmp <= V) {
        tmp *= 2;
        MAX_LOG_N++;
      }
    }
    parent.resize(MAX_LOG_N, vector<int>(V));
    depth.resize(V);
    order.resize(V);
    G = _G;
    int tmp = 0;
    dfs(root, -1, 0, tmp);
    for (int k = 0; k + 1 < MAX_LOG_N; k++) {
      for (int v = 0; v < V; v++) {
        if (parent[k][v] < 0)
          parent[k + 1][v] = -1;
        else
          parent[k + 1][v] = parent[k][parent[k][v]];
      }
    }
  }
  int get_kth_parent(int v, int k) {
    for (int i = MAX_LOG_N - 1; i >= 0; i--) {
      if ((1 << i) > k) continue;
      v = parent[i][v];
      k -= (1 << i);
    }
    return v;
  }
  int lca(int u, int v) {
    if (depth[u] > depth[v]) swap(u, v);
    for (int k = 0; k < MAX_LOG_N; k++) {
      if ((depth[v] - depth[u]) >> k & 1) {
        v = parent[k][v];
      }
    }
    if (u == v) return u;
    for (int k = MAX_LOG_N - 1; k >= 0; k--) {
      if (parent[k][u] != parent[k][v]) {
        u = parent[k][u];
        v = parent[k][v];
      }
    }
    return parent[0][u];
  }
  int distance(int u, int v) {
    return depth[u] + depth[v] - depth[lca(u, v)] * 2;
  }
};
vector<pair<pair<int, int>, int>> compress_tree(LCA& lca, vector<int>& vers) {
  vector<pair<pair<int, int>, int>> ret;
  sort(vers.begin(), vers.end(),
       [&](const int& l, const int& r) { return lca.order[l] < lca.order[r]; });
  int N = vers.size();
  for (int j = 1; j < N; j++) {
    int com = lca.lca(vers[j - 1], vers[j]);
    vers.push_back(com);
  }
  sort(vers.begin(), vers.end());
  vers.erase(unique(vers.begin(), vers.end()), vers.end());
  N = vers.size();
  sort(vers.begin(), vers.end(),
       [&](const int& l, const int& r) { return lca.order[l] < lca.order[r]; });
  vector<int> sta;
  sta.push_back(vers[0]);
  for (int j = 1; j < N; j++) {
    while (true) {
      if (lca.lca(sta.back(), vers[j]) == sta.back()) break;
      sta.pop_back();
    }
    ret.push_back(
        pair<pair<int, int>, int>(pair<int, int>(sta.back(), vers[j]),
                                  lca.depth[vers[j]] - lca.depth[sta.back()]));
    sta.push_back(vers[j]);
  }
  return ret;
}
int n;
vector<vector<int>> e;
vector<pair<int, int>> e2[200000];
int v[200000], s[200000], u[200000];
int rv[200000], ru[200000];
long long dist[200000];
int infe[200000];
LCA lca;
int main() {
  scanf("%d", &n);
  e.resize(n);
  for (int i = 0; i < (int)n - 1; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    x--;
    y--;
    e[x].push_back(y);
    e[y].push_back(x);
  }
  lca.init(n, e, 0);
  int q;
  scanf("%d", &q);
  memset(rv, -1, sizeof(rv));
  memset(ru, -1, sizeof(ru));
  for (int i = 0; i < (int)q; i++) {
    int k, m;
    scanf("%d%d", &k, &m);
    vector<int> vers(k + m);
    for (int j = 0; j < (int)k; j++) {
      scanf("%d%d", v + j, s + j);
      v[j]--;
      vers[j] = v[j];
      rv[v[j]] = j;
    }
    for (int j = 0; j < (int)m; j++) {
      scanf("%d", u + j);
      u[j]--;
      vers[j + k] = u[j];
      ru[u[j]] = j;
    }
    vector<pair<pair<int, int>, int>> ee = compress_tree(lca, vers);
    for (pair<pair<int, int>, int> eel : ee) {
      e2[eel.first.first].push_back(
          pair<int, int>(eel.first.second, eel.second));
      e2[eel.first.second].push_back(
          pair<int, int>(eel.first.first, eel.second));
    }
    priority_queue<pair<pair<long long, long long>, int>,
                   vector<pair<pair<long long, long long>, int>>,
                   greater<pair<pair<long long, long long>, int>>>
        que;
    for (int ve : vers) {
      dist[ve] = linf;
      infe[ve] = -1;
      if (rv[ve] != -1) {
        dist[ve] = 0;
        infe[ve] = rv[ve];
        que.push(pair<pair<long long, long long>, int>(
            pair<long long, long long>(
                (dist[ve] + s[infe[ve]] - 1) / s[infe[ve]], infe[ve]),
            ve));
      }
    }
    while (!que.empty()) {
      pair<pair<long long, long long>, int> q = que.top();
      que.pop();
      for (pair<int, int> E : e2[q.second]) {
        int to = E.first, cost = E.second;
        if (infe[to] == -1) {
          dist[to] = dist[q.second] + cost;
          infe[to] = infe[q.second];
          que.push(pair<pair<long long, long long>, int>(
              pair<long long, long long>(
                  (dist[to] + s[infe[to]] - 1) / s[infe[to]], infe[to]),
              to));
          continue;
        }
        long long ti = (dist[to] + s[infe[to]] - 1) / s[infe[to]];
        if (pair<long long, long long>(ti, infe[to]) >
            pair<long long, long long>(
                (dist[q.second] + cost + s[infe[q.second]] - 1) /
                    s[infe[q.second]],
                infe[q.second])) {
          dist[to] = dist[q.second] + cost;
          infe[to] = infe[q.second];
          que.push(pair<pair<long long, long long>, int>(
              pair<long long, long long>(
                  (dist[to] + s[infe[to]] - 1) / s[infe[to]], infe[to]),
              to));
        }
      }
    }
    vector<int> out(m);
    for (int ve : vers) {
      if (ru[ve] == -1) continue;
      out[ru[ve]] = infe[ve] + 1;
    }
    for (int o : out) printf("%d ", o);
    puts("");
    for (int ve : vers) e2[ve].clear();
    for (int j = 0; j < (int)k; j++) {
      rv[v[j]] = -1;
    }
    for (int j = 0; j < (int)m; j++) {
      ru[u[j]] = -1;
    }
  }
}