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;
const int MOD = 1000000007;
const long long BIG = 1446803456761533460;
const int Big = 336860180;
stringstream sss;
const int maxn = 200010;
const int maxnlg = 20;
int n, Q, k, m;
vector<int> g[maxn], subt[maxn];
vector<pair<int, int>> gg[maxn];
int st[maxn], ft[maxn], pars[maxnlg][maxn], ht[maxn];
int lt[maxn], imp[maxn];
pair<int, int> virus[maxn];
vector<int> ver;
priority_queue<pair<pair<int, int>, pair<int, int>>,
               vector<pair<pair<int, int>, pair<int, int>>>,
               greater<pair<pair<int, int>, pair<int, int>>>>
    heap;
int col[maxn];
int tim = 0;
void dfs_lca(int x, int par) {
  st[x] = tim++;
  pars[0][x] = par;
  for (int i = (0); i < (maxnlg - 1); ++i) pars[i + 1][x] = pars[i][pars[i][x]];
  for (auto y : g[x])
    if (y != par) {
      ht[y] = ht[x] + 1;
      dfs_lca(y, x);
    }
  ft[x] = tim;
}
int LCA(int a, int b) {
  if (st[a] > st[b]) swap(a, b);
  if (ft[a] >= ft[b]) return a;
  for (int i = (maxnlg)-1; i >= (0); --i) {
    if (ft[pars[i][a]] < ft[b]) a = pars[i][a];
  }
  return pars[0][a];
}
bool st_cmp(int a, int b) { return st[a] < st[b]; }
void MAIN() {
  cin >> n;
  for (int i = (0); i < (n - 1); ++i) {
    int a, b;
    cin >> a >> b;
    g[a].emplace_back(b), g[b].emplace_back(a);
  }
  g[0].emplace_back(1);
  dfs_lca(0, 0);
  cin >> Q;
  for (int q = (0); q < (Q); ++q) {
    cin >> k >> m;
    for (int i = (0); i < (k); ++i) {
      int v, s;
      cin >> v >> s;
      virus[i] = {v, s};
      ver.emplace_back(v);
    }
    for (int i = (0); i < (m); ++i) {
      int v;
      cin >> v;
      imp[i] = v;
      ver.emplace_back(v);
    }
    ver.emplace_back(0);
    sort((ver).begin(), (ver).end(), st_cmp);
    ver.resize(unique((ver).begin(), (ver).end()) - ver.begin());
    int sz = ver.size();
    for (int i = (0); i < (sz - 1); ++i)
      ver.emplace_back(LCA(ver[i], ver[i + 1]));
    sort((ver).begin(), (ver).end(), st_cmp);
    ver.resize(unique((ver).begin(), (ver).end()) - ver.begin());
    sz = ver.size();
    for (int i = (1); i < (sz); ++i) {
      lt[i] = i - 1;
      while (lt[i] > 0 && ft[ver[lt[i]]] < ft[ver[i]]) lt[i] = lt[lt[i]];
      gg[ver[i]].emplace_back(ver[lt[i]], ht[ver[i]] - ht[ver[lt[i]]]);
      gg[ver[lt[i]]].emplace_back(ver[i], ht[ver[i]] - ht[ver[lt[i]]]);
    }
    for (int i = (0); i < (k); ++i) {
      int v = virus[i].first;
      heap.push({{0, i}, {v, 0}});
    }
    while (!heap.empty()) {
      pair<pair<int, int>, pair<int, int>> x = heap.top();
      heap.pop();
      if (col[x.second.first]) continue;
      col[x.second.first] = x.first.second + 1;
      for (auto y : gg[x.second.first]) {
        if (col[y.first] == 0) {
          int d = x.second.second + y.second;
          int s = virus[x.first.second].second;
          heap.push({{(d + s - 1) / s, x.first.second}, {y.first, d}});
        }
      }
    }
    for (int i = (0); i < (m); ++i) cout << col[imp[i]] << ' ';
    cout << '\n';
    for (auto x : ver) col[x] = 0, gg[x].clear();
    ver.clear();
  }
}
int main() {
  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cout << fixed << setprecision(10);
  sss << R"(
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
    )";
  MAIN();
  return 0;
}