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;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<vector<int>> g(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);
  }
  vector<int> dfn(n, -1), dep(n);
  vector<vector<int>> fa(n);
  function<void(int, int)> Dfs = [&](int x, int p) {
    static int tk = 0;
    dfn[x] = tk++;
    dep[x] = ~p ? dep[p] + 1 : 0;
    fa[x].push_back(p);
    for (int i = 1; (1 << i) <= dep[x]; ++i)
      fa[x].push_back(fa[fa[x][i - 1]][i - 1]);
    for (int u : g[x]) {
      if (u == p) continue;
      Dfs(u, x);
    }
  };
  auto GetLCA = [&](int u, int v) {
    if (dep[u] > dep[v]) swap(u, v);
    for (int i = 0; i < fa[v].size(); ++i) {
      if ((dep[v] - dep[u]) >> i & 1) v = fa[v][i];
    }
    if (u == v) return u;
    for (int i = 20; i >= 0; --i) {
      if (i < fa[u].size() && i < fa[v].size() && fa[u][i] != fa[v][i]) {
        u = fa[u][i];
        v = fa[v][i];
      }
    }
    return fa[u][0];
  };
  vector<vector<pair<int, int>>> virt(n);
  vector<int> used;
  auto Dist = [&](int u, int v) {
    return dep[u] + dep[v] - 2 * dep[GetLCA(u, v)];
  };
  auto BuildVirtualTree = [&](vector<int> v) {
    v.push_back(0);
    sort(v.begin(), v.end(), [&](int i, int j) { return dfn[i] < dfn[j]; });
    v.resize(unique(v.begin(), v.end()) - v.begin());
    for (int u : v) used.push_back(u);
    auto AddEdge = [&](int u, int v) {
      virt[u].emplace_back(v, Dist(u, v));
      virt[v].emplace_back(u, Dist(u, v));
      used.push_back(u);
      used.push_back(v);
    };
    vector<int> stk;
    for (int u : v) {
      if (stk.empty()) {
        stk.push_back(u);
        continue;
      }
      int p = GetLCA(u, stk.back());
      if (p == stk.back()) {
        stk.push_back(u);
        continue;
      }
      while (stk.size() >= 2 && dep[p] <= dep[stk[stk.size() - 2]]) {
        int x = stk.back();
        stk.pop_back();
        AddEdge(x, stk.back());
      }
      if (stk.back() != p) {
        AddEdge(stk.back(), p);
        stk.pop_back();
        stk.push_back(p);
      }
      stk.push_back(u);
    }
    for (int i = 0; i + 1 < stk.size(); ++i) AddEdge(stk[i], stk[i + 1]);
  };
  vector<int> spr(n, -1), dp(n, -1), mark(n, -1), rd(n, -1), vis(n, 0);
  auto Recover = [&]() {
    for (int u : used) {
      virt[u].clear();
      spr[u] = -1;
      dp[u] = -1;
      mark[u] = -1;
      rd[u] = -1;
      vis[u] = 0;
    }
    used.clear();
  };
  auto Solve = [&](const vector<int> &v, const vector<int> &u) {
    priority_queue<tuple<int, int, int>> pq;
    for (int i = 0; i < v.size(); ++i) {
      mark[v[i]] = i;
      dp[v[i]] = 0;
      rd[v[i]] = 0;
      pq.emplace(0, -i, v[i]);
    }
    while (!pq.empty()) {
      int x = get<2>(pq.top());
      pq.pop();
      if (vis[x]++) continue;
      for (auto &e : virt[x]) {
        int u = e.first, w = e.second;
        int sum = dp[x] * spr[x] - rd[x] + w;
        int ndp = (sum + spr[x] - 1) / spr[x];
        int ndist = (sum + spr[x] - 1) / spr[x] * spr[x] - sum;
        if (mark[u] == -1 ||
            mark[u] != -1 &&
                (ndp < dp[u] || ndp == dp[u] && mark[x] < mark[u] ||
                 ndp == dp[u] && mark[x] == mark[u] && ndist > rd[u])) {
          mark[u] = mark[x];
          dp[u] = ndp;
          rd[u] = ndist;
          spr[u] = spr[x];
          pq.emplace(-dp[u], -mark[u], u);
        }
      }
    }
    for (int i : u) cout << mark[i] + 1 << ' ';
    cout << "\n";
  };
  Dfs(0, -1);
  int q;
  cin >> q;
  while (q--) {
    int k, m;
    cin >> k >> m;
    vector<int> v(k), s(k), u(m), uniq;
    set<int> uf;
    for (int i = 0; i < k; ++i) {
      cin >> v[i] >> s[i];
      v[i]--;
      uniq.push_back(v[i]);
      spr[v[i]] = s[i];
      uf.insert(v[i]);
    }
    for (int i = 0; i < m; ++i) {
      cin >> u[i];
      u[i]--;
      uniq.push_back(u[i]);
    }
    sort(uniq.begin(), uniq.end());
    uniq.resize(unique(uniq.begin(), uniq.end()) - uniq.begin());
    BuildVirtualTree(uniq);
    Solve(v, u);
    Recover();
  }
  return 0;
}