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>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,mmx,avx")
using namespace std;
const int MOD = 1000000007;
const int UNDEF = -1;
const int INF = 1 << 30;
template <typename T>
inline bool chkmax(T &aa, T bb) {
  return aa < bb ? aa = bb, true : false;
}
template <typename T>
inline bool chkmin(T &aa, T bb) {
  return aa > bb ? aa = bb, true : false;
}
int rint();
char rch();
long long rlong();
const int mn = (2e5) + 4;
template <typename T>
void makeunique(vector<T> &vx) {
  sort(vx.begin(), vx.end());
  auto it = unique(vx.begin(), vx.end());
  vx.resize(std::distance(vx.begin(), it));
}
template <typename T>
int bins(vector<T> &vx, T x) {
  int imin = 0, imax = vx.size();
  while (imin < imax) {
    int imid = (imin + imax) >> 1;
    if (vx[imid] < x)
      imin = imid + 1;
    else
      imax = imid;
  }
  return imin;
}
class LcaSvparseTable {
 public:
  int len = 0;
  int **up;
  int *tin;
  int *tout;
  int timestamp = 0;
  int *vdepth;
  void dfs(vector<vector<int> > &tree, int u, int p, int depth) {
    vdepth[u] = depth;
    tin[u] = timestamp++;
    up[0][u] = p;
    for (int i = 1; i < len; i++) up[i][u] = up[i - 1][up[i - 1][u]];
    for (int v : tree[u])
      if (v != p) dfs(tree, v, u, depth + 1);
    tout[u] = timestamp++;
  }
  void init(vector<vector<int> > &tree, int root) {
    int n = tree.size();
    len = 1;
    while ((1 << len) <= n) ++len;
    up = new int *[len];
    for (int i = 0; i < len; i++) {
      up[i] = new int[n];
      memset(up[i], 0, sizeof(up[i][0]) * n);
    }
    tin = new int[n];
    memset(tin, 0, sizeof(tin[0]) * n);
    tout = new int[n];
    memset(tout, 0, sizeof(tout[0] * n));
    vdepth = new int[n];
    memset(vdepth, 0, sizeof(vdepth[0] * n));
    dfs(tree, root, root, 0);
  }
  bool isParent(int vparent, int child) {
    return tin[vparent] <= tin[child] && tout[child] <= tout[vparent];
  }
  int lca(int oa, int ob) {
    int a = oa, b = ob;
    if (isParent(a, b)) return a;
    if (isParent(b, a)) return b;
    for (int i = len - 1; i >= 0; i--)
      if (!isParent(up[i][a], b)) a = up[i][a];
    int ancestor = up[0][a];
    return ancestor;
  }
};
LcaSvparseTable L;
const int mx = mn;
int gdepth[mn];
class UnionFind {
 public:
  inline int combine(int x, int y) { return (gdepth[x] < gdepth[y]) ? x : y; }
  inline int getInitialValue(int x) { return x; }
  int ufParent[mx];
  int rank[mx];
  int ufData[mx];
  inline void ufreset(int x) {
    ufParent[x] = x;
    ufData[x] = getInitialValue(x);
    rank[x] = 0;
  }
  void init(int n) {
    for (int x = 0; x < n; x++) {
      ufreset(x);
    }
  }
  int ffind(int x) {
    if (ufParent[x] != x) {
      ufParent[x] = ffind(ufParent[x]);
    }
    return ufParent[x];
  }
  void funion(int _x, int _y) {
    int xr = ffind(_x);
    int yr = ffind(_y);
    if (xr == yr) return;
    if (rank[xr] > rank[yr]) swap(xr, yr);
    if (rank[xr] == rank[yr]) rank[yr]++;
    ufParent[xr] = yr;
    ufData[yr] = combine(ufData[xr], ufData[yr]);
  }
  int getData(int x) { return ufData[ffind(x)]; }
};
UnionFind uf;
vector<vector<int> > g;
int center[mn], speed[mn], impt[mn], va[mn];
pair<int, int> vpar[mn];
vector<vector<pair<int, int> > > h;
pair<int, int> vtimevir[mn];
int rem[mn];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n = rint();
  g.resize(n + 1);
  for (int i = 1; i < n; i++) {
    int x = rint(), y = rint();
    g[x].push_back(y);
    g[y].push_back(x);
  }
  L.init(g, 1);
  int qn = rint();
  for (int qi = 0; qi < qn; qi++) {
    int nv = rint();
    int nc = rint();
    for (int k = 0; k < nv; k++) {
      center[k] = rint();
      speed[k] = rint();
    }
    for (int ci = 0; ci < nc; ci++) {
      impt[ci] = rint();
    }
    vector<pair<int, int> > ev;
    ev.reserve(nv + nc);
    for (int k = 0; k < nv; k++) {
      int x = center[k];
      ev.push_back(make_pair(L.tin[x], x));
    }
    for (int ci = 0; ci < nc; ci++) {
      int x = impt[ci];
      ev.push_back(make_pair(L.tin[x], x));
    }
    makeunique(ev);
    int evsz = ev.size();
    vector<int> allv;
    allv.reserve(2 * evsz - 1);
    for (auto &w : ev) {
      allv.push_back(w.second);
      vpar[w.second] = make_pair(INF, INF);
    }
    vector<pair<int, pair<int, pair<int, int> > > > vda;
    vda.reserve(evsz - 1);
    for (int i = 1; i < evsz; i++) {
      int l = ev[i - 1].second;
      int r = ev[i].second;
      int a = L.lca(l, r);
      if (a != l && a != r) allv.push_back(a);
      vda.push_back(make_pair(-L.vdepth[a], make_pair(a, make_pair(l, r))));
    }
    sort(vda.begin(), vda.end());
    makeunique(allv);
    h.clear();
    h.resize(allv.size());
    uf.init(allv.size());
    for (int x = 0; x < allv.size(); x++) gdepth[x] = L.vdepth[allv[x]];
    for (auto &w : vda) {
      int a = bins(allv, w.second.first);
      int x[2];
      x[0] = uf.getData(bins(allv, w.second.second.first));
      x[1] = uf.getData(bins(allv, w.second.second.second));
      for (int t = 0; t < 2; t++) {
        int l = x[t];
        if (l != a) {
          int d = gdepth[l] - gdepth[a];
          h[a].push_back(make_pair(l, d));
          h[l].push_back(make_pair(a, d));
          uf.funion(a, l);
        }
      }
    }
    int hsz = h.size();
    using pqt = pair<pair<int, int>, int>;
    priority_queue<pqt, vector<pqt>, greater<pqt> > pq;
    for (int x = 0; x < hsz; x++) {
      vtimevir[x] = make_pair(INF, INF);
      rem[x] = INF;
    }
    for (int k = 0; k < nv; k++) {
      int x = bins(allv, center[k]);
      vtimevir[x] = make_pair(0, k);
      rem[x] = 0;
      pq.push(make_pair(vtimevir[x], x));
    }
    while (!pq.empty()) {
      auto got = pq.top();
      pq.pop();
      int x = got.second;
      if (got.first != vtimevir[x]) continue;
      int time = got.first.first;
      int vir = got.first.second;
      for (auto &yd : h[x]) {
        int y = yd.first, dist = yd.second;
        int remy = rem[x] - dist;
        int ntime;
        if (remy >= 0) {
          ntime = time;
        } else {
          remy = -remy;
          int needtime = (remy + speed[vir] - 1) / speed[vir];
          ntime = time + needtime;
          remy = needtime * speed[vir] - remy;
        }
        pair<int, int> ntimevir = make_pair(ntime, vir);
        if (ntimevir < vtimevir[y]) {
          rem[y] = remy;
          vtimevir[y] = ntimevir;
          pq.push(make_pair(ntimevir, y));
        }
      }
    }
    for (int ci = 0; ci < nc; ci++) {
      int x = bins(allv, impt[ci]);
      printf("%d ", vtimevir[x].second + 1);
    }
    printf("\n");
  }
}
static char stdinBuffer[1024];
static char *stdinDataEnd = stdinBuffer + sizeof(stdinBuffer);
static const char *stdinPos = stdinDataEnd;
void readAhead(size_t amount) {
  size_t remaining = stdinDataEnd - stdinPos;
  if (remaining < amount) {
    memmove(stdinBuffer, stdinPos, remaining);
    size_t sz = fread(stdinBuffer + remaining, 1,
                      sizeof(stdinBuffer) - remaining, stdin);
    stdinPos = stdinBuffer;
    stdinDataEnd = stdinBuffer + remaining + sz;
    if (stdinDataEnd != stdinBuffer + sizeof(stdinBuffer)) *stdinDataEnd = 0;
  }
}
int rint() {
  readAhead(16);
  int x = 0;
  bool neg = false;
  while (*stdinPos == ' ' || *stdinPos == '\n') ++stdinPos;
  if (*stdinPos == '-') {
    ++stdinPos;
    neg = true;
  }
  while (*stdinPos >= '0' && *stdinPos <= '9') {
    x *= 10;
    x += *stdinPos - '0';
    ++stdinPos;
  }
  return neg ? -x : x;
}
char rch() {
  readAhead(16);
  while (*stdinPos == ' ' || *stdinPos == '\n') ++stdinPos;
  char ans = *stdinPos;
  ++stdinPos;
  return ans;
}
long long rlong() {
  readAhead(32);
  long long x = 0;
  bool neg = false;
  while (*stdinPos == ' ' || *stdinPos == '\n') ++stdinPos;
  if (*stdinPos == '-') {
    ++stdinPos;
    neg = true;
  }
  while (*stdinPos >= '0' && *stdinPos <= '9') {
    x *= 10;
    x += *stdinPos - '0';
    ++stdinPos;
  }
  return neg ? -x : x;
}