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;
using ll = long long;
using ld = long double;
using pll = pair<ll, ll>;
using vll = vector<ll>;
using vpll = vector<pll>;
using gr = vector<vll>;
using wgr = vector<vpll>;
struct d_ {
  template <typename T>
  d_ &operator,(const T &x) {
    cerr << ' ' << x;
    return *this;
  }
  template <typename T>
  d_ &operator,(const vector<T> &x) {
    for (auto x : x) cerr << ' ' << x;
    return *this;
  }
} d_t;
const int MX = 2 * 1e5 + 7;
ll n = 0;
vll ng[MX];
ll depth[MX];
ll par[MX];
void calc_depth(ll u = 0, ll p = -1, ll d = 0) {
  depth[u] = d;
  par[u] = p;
  for (auto v : ng[u])
    if (v != p) calc_depth(v, u, d + 1);
}
struct Event {
  ll vid, v, s;
  ll lca = -1;
  Event() {}
  Event(ll vid, ll v, ll s) : vid(vid), v(v), s(s) {}
  ll distTo(ll u) const {
    if (~lca)
      return depth[u] + depth[v] - 2 * depth[lca];
    else
      return abs(depth[u] - depth[v]);
  }
  ll stepsTo(ll u) const {
    ll d = distTo(u);
    return (d + s - 1) / s;
  }
  bool slowerThanTo(const Event &e2, ll u) const {
    ll d1 = distTo(u), d2 = e2.distTo(u);
    ll s1 = stepsTo(u), s2 = e2.stepsTo(u);
    return (s1 > s2 || (s2 == s1 && vid > e2.vid) ||
            (s1 == s2 && vid == e2.vid && d1 > d2));
  }
  void db(ll u) { ; }
};
map<ll, Event> fromDwn[MX];
map<ll, map<ll, ll>> ans;
map<ll, stack<Event>> fromUp;
struct Box {
  map<ll, Event> evs;
  set<ll> imps;
  ll cnt = 0;
  void add(ll qid, const Event &ev, ll v = -1) {
    if (evs.count(qid) == 0) {
      evs[qid] = ev;
      cnt++;
    } else {
      assert(v >= 0);
      Event &cur = evs[qid];
      if (cur.slowerThanTo(ev, v)) evs[qid] = ev;
    }
  }
  void addImp(ll qid) { imps.insert(qid); }
  ll size() { return cnt + imps.size(); }
  void apply(Box &own, ll v) {
    ;
    for (auto &ev : own.evs) {
      fromDwn[v][ev.first] = evs[ev.first] = ev.second;
      ;
      ev.second.db(v);
    }
    for (auto qid : own.imps) {
      if (evs.count(qid)) fromDwn[v][qid] = evs[qid];
    }
    imps.insert(begin(own.imps), end(own.imps));
  }
  void merge(Box *bx, ll v) {
    ;
    set<ll> onCrossQids;
    for (auto &qid : bx->imps)
      if (evs.count(qid)) onCrossQids.insert(qid);
    for (auto &ev : bx->evs) {
      ll qid = ev.first;
      if (imps.count(qid)) onCrossQids.insert(qid);
      if (evs.count(qid)) {
        ;
        evs[qid].db(v);
        ev.second.db(v);
      }
      add(qid, ev.second, v);
    }
    for (auto qid : onCrossQids) {
      fromDwn[v][qid] = evs[qid];
      ;
      evs[qid].db(v);
    }
    imps.insert(begin(bx->imps), end(bx->imps));
  }
};
Box *bxs[MX];
Box own[MX];
void topDown(ll u = 0) {
  set<ll> pushed;
  for (auto &imp : own[u].imps) {
    if (own[u].evs.count(imp)) {
      ans[imp][u] = own[u].evs[imp].vid;
      continue;
    }
    Event *e1 = 0, *e2 = 0;
    if (fromUp[imp].size()) e1 = &fromUp[imp].top();
    if (fromDwn[u].count(imp)) e2 = &fromDwn[u][imp];
    assert(e1 != 0 || e2 != 0);
    if (!e1) {
      e1 = e2;
      e2 = nullptr;
    }
    if (e1 && e2) {
      if (e1->slowerThanTo(*e2, u)) swap(e1, e2);
    };
    ;
    if (e1) e1->db(u);
    if (e2) e2->db(u);
    ans[imp][u] = e1->vid;
  }
  for (auto &ev : fromDwn[u]) {
    if (fromUp[ev.first].empty()) {
      Event frmDwnEv = ev.second;
      frmDwnEv.lca = u;
      fromUp[ev.first].push(frmDwnEv);
      pushed.insert(ev.first);
    } else {
      Event ev1 = ev.second;
      ev1.lca = u;
      Event ev2 = fromUp[ev.first].top();
      ;
      ev1.db(u);
      ev2.db(u);
      if (ev2.slowerThanTo(ev1, u)) {
        fromUp[ev.first].push(ev1);
        pushed.insert(ev.first);
      }
    }
  }
  for (auto &ev : own[u].evs) fromUp[ev.first].push(ev.second);
  for (auto v : ng[u])
    if (v != par[u]) topDown(v);
  for (auto &ev : own[u].evs) fromUp[ev.first].pop();
  for (auto &ev : fromDwn[u])
    if (pushed.count(ev.first)) fromUp[ev.first].pop();
}
int main(void) {
  ios_base::sync_with_stdio(false);
  cin >> n;
  for (ll i(0); i < n - 1; i++) {
    ll u, v;
    cin >> u >> v;
    u--, v--;
    ng[u].push_back(v), ng[v].push_back(u);
  }
  vll deg(n);
  queue<ll> q;
  calc_depth();
  for (ll i(1); i < n; i++) deg[par[i]]++;
  for (ll i(0); i < n; i++)
    if (deg[i] == 0) q.push(i);
  for (ll i(0); i < n; i++) bxs[i] = new Box();
  ll r;
  cin >> r;
  vector<vll> impQs(r);
  for (ll i(0); i < r; i++) {
    ll k, m;
    cin >> k >> m;
    for (ll j(0); j < k; j++) {
      ll v, s;
      cin >> v >> s;
      v--;
      own[v].add(i, {j, v, s});
    }
    for (ll j(0); j < m; j++) {
      ll v;
      cin >> v;
      v--;
      own[v].addImp(i);
      impQs[i].push_back(v);
    }
  }
  while (q.size()) {
    ll u = q.front();
    q.pop();
    ;
    bxs[u]->apply(own[u], u);
    if (u == 0) break;
    ll v = par[u];
    if (bxs[v]->size() < bxs[u]->size()) swap(bxs[v], bxs[u]);
    bxs[v]->merge(bxs[u], v);
    deg[v]--;
    if (deg[v] == 0) q.push(v);
  }
  topDown();
  for (ll i(0); i < r; i++) {
    for (auto u : impQs[i]) cout << ans[i][u] + 1 << ' ';
    cout << endl;
  }
  return 0;
}