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());
namespace LCA {
vector<vector<int>> G;
int root;
int MAX_LOG_N;
vector<vector<int>> parent;
vector<int> depth;
void dfs(int v, int p, int d) {
  parent[0][v] = p;
  depth[v] = d;
  for (int i = 0; i < (int)G[v].size(); i++) {
    if (G[v][i] != p) dfs(G[v][i], v, d + 1);
  }
}
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);
  G = _G;
  dfs(root, -1, 0);
  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];
}
}  // namespace LCA
int n;
vector<vector<int>> e;
vector<pair<int, int>> e2[200000];
int ord[200000];
int v[200000], s[200000], u[200000];
int rv[200000], ru[200000];
long long dist[200000];
int infe[200000];
void dfs(int v, int p, int& pos) {
  ord[v] = pos++;
  for (int to : e[v]) {
    if (to == p) continue;
    dfs(to, v, pos);
  }
}
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);
  }
  int tmp = 0;
  dfs(0, -1, tmp);
  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;
    }
    sort(vers.begin(), vers.end(),
         [&](const int& l, const int& r) { return ord[l] < ord[r]; });
    for (int j = 1; j < k + m; 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());
    int N = vers.size();
    sort(vers.begin(), vers.end(),
         [&](const int& l, const int& r) { return ord[l] < ord[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();
      }
      e2[sta.back()].push_back(pair<int, int>(
          vers[j], LCA::depth[vers[j]] - LCA::depth[sta.back()]));
      e2[vers[j]].push_back(pair<int, int>(
          sta.back(), LCA::depth[vers[j]] - LCA::depth[sta.back()]));
      sta.push_back(vers[j]);
    }
    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;
    }
  }
}