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;
template <typename T>
inline bool upmin(T &x, T y) {
  return y < x ? x = y, 1 : 0;
}
template <typename T>
inline bool upmax(T &x, T y) {
  return x < y ? x = y, 1 : 0;
}
const long double eps = 1e-9;
const long double pi = acos(-1);
const int oo = 1 << 30;
const long long loo = 1ll << 60;
const int mods = 998244353;
const int MAXN = 400005;
const int INF = 0x3f3f3f3f;
namespace FastIO {
constexpr int SIZE = (1 << 21) + 1;
int num = 0, f;
char ibuf[SIZE], obuf[SIZE], que[65], *iS, *iT, *oS = obuf,
                                                *oT = obuf + SIZE - 1, c;
inline void flush() {
  fwrite(obuf, 1, oS - obuf, stdout);
  oS = obuf;
}
inline void putc(char c) {
  *oS++ = c;
  if (oS == oT) flush();
}
inline void getc(char &c) {
  for (c = (iS == iT ? (iT = ((iS = ibuf) + fread(ibuf, 1, SIZE, stdin)),
                       (iS == iT ? EOF : *iS++))
                     : *iS++);
       (c < 'a' || c > 'z') && c != EOF;
       c = (iS == iT ? (iT = ((iS = ibuf) + fread(ibuf, 1, SIZE, stdin)),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    ;
}
inline void reads(char *st) {
  char c;
  int n = 0;
  getc(st[++n]);
  for (c = (iS == iT ? (iT = ((iS = ibuf) + fread(ibuf, 1, SIZE, stdin)),
                       (iS == iT ? EOF : *iS++))
                     : *iS++);
       c >= 'a' && c <= 'z';
       c = (iS == iT ? (iT = ((iS = ibuf) + fread(ibuf, 1, SIZE, stdin)),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    st[++n] = c;
}
template <class I>
inline void read(I &x) {
  for (f = 1, c = (iS == iT ? (iT = ((iS = ibuf) + fread(ibuf, 1, SIZE, stdin)),
                              (iS == iT ? EOF : *iS++))
                            : *iS++);
       c < '0' || c > '9';
       c = (iS == iT ? (iT = ((iS = ibuf) + fread(ibuf, 1, SIZE, stdin)),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    if (c == '-') f = -1;
  for (x = 0; c >= '0' && c <= '9';
       c = (iS == iT ? (iT = ((iS = ibuf) + fread(ibuf, 1, SIZE, stdin)),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    x = (x << 3) + (x << 1) + (c & 15);
  x *= f;
}
template <class I>
inline void print(I x) {
  if (x < 0) putc('-'), x = -x;
  if (!x) putc('0');
  while (x) que[++num] = x % 10 + 48, x /= 10;
  while (num) putc(que[num--]);
}
struct Flusher_ {
  ~Flusher_() { flush(); }
} io_Flusher_;
}  // namespace FastIO
using FastIO ::print;
using FastIO ::putc;
using FastIO ::read;
using FastIO ::reads;
pair<int, int> a[MAXN];
vector<int> V, E[MAXN], e[MAXN];
int n, m, K, Case, dfn[MAXN], vis[MAXN], fa[MAXN][20], dep[MAXN], stk[MAXN],
    Q[MAXN], Log[MAXN], DFN = 0, top;
struct dnode {
  int x, y, z, id;
  friend bool operator<(const dnode &a, const dnode &b) {
    if (a.x != b.x) return a.x > b.x;
    if (a.y != b.y) return a.y > b.y;
    return a.z > b.z;
  }
} dist[MAXN];
priority_queue<dnode> heap;
int getlca(int x, int y) {
  if (dep[x] < dep[y]) swap(x, y);
  for (int i = Log[dep[x]]; i >= 0; --i)
    if (dep[fa[x][i]] >= dep[y]) x = fa[x][i];
  if (x == y) return x;
  for (int i = Log[dep[x]]; i >= 0; --i)
    if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
  return fa[x][0];
}
void dfs(int x, int father) {
  dist[x] = (dnode){INF, INF, INF, x};
  dfn[x] = ++DFN, fa[x][0] = father, dep[x] = dep[father] + 1;
  for (int i = 1; i <= Log[dep[x]]; ++i) fa[x][i] = fa[fa[x][i - 1]][i - 1];
  for (auto v : e[x]) {
    if (v == father) continue;
    dfs(v, x);
  }
}
void clean(int x, int father) {
  for (auto v : E[x])
    if (v != father) clean(v, x);
  E[x].clear(), vis[x] = 0, dist[x] = (dnode){INF, INF, INF, x};
}
void add(int u, int v) { E[u].push_back(v), E[v].push_back(u); }
void build() {
  int lst = 1;
  stk[top = 1] = 1;
  for (auto v : V) {
    if (v == lst) continue;
    int lca = getlca(stk[top], v);
    while (top > 1 && dep[stk[top - 1]] > dep[lca])
      add(stk[top - 1], stk[top]), --top;
    if (dep[stk[top]] > dep[lca]) add(lca, stk[top--]);
    if (stk[top] != lca) stk[++top] = lca;
    stk[++top] = v, lst = v;
  }
  while (top > 1) add(stk[top - 1], stk[top]), --top;
}
void solve() {
  for (int i = 1; i <= K; ++i)
    dist[a[i].first] = (dnode){0, i, 0, a[i].first},
    heap.push(dist[a[i].first]), dist[a[i].first].x = -1;
  while (!heap.empty()) {
    dnode nw = heap.top();
    heap.pop();
    if (vis[nw.id]) continue;
    vis[nw.id] = 1;
    for (auto v : E[nw.id]) {
      dnode p;
      p.y = nw.y;
      p.z = nw.z + abs(dep[nw.id] - dep[v]);
      int t = (p.z - 1) / a[p.y].second;
      p.x = nw.x + t;
      p.z -= t * a[p.y].second;
      p.id = v;
      if (dist[v] < p) dist[v] = p, heap.push(p);
    }
  }
  for (int i = 1; i <= m; ++i) print(dist[Q[i]].y), putc(' ');
  putc('\n');
}
signed main() {
  read(n);
  Log[1] = 0;
  for (int i = 2; i <= n; ++i) Log[i] = Log[i >> 1] + 1;
  for (int i = 1, u, v; i < n; ++i)
    read(u), read(v), e[u].push_back(v), e[v].push_back(u);
  dep[0] = -1, dfs(1, 0);
  read(Case);
  while (Case--) {
    read(K), read(m);
    for (int i = 1; i <= K; ++i)
      read(a[i].first), read(a[i].second), V.push_back(a[i].first);
    for (int i = 1; i <= m; ++i) read(Q[i]), V.push_back(Q[i]);
    sort(V.begin(), V.end(), [&](int x, int y) { return dfn[x] < dfn[y]; });
    build();
    solve();
    clean(1, 0);
    V.clear();
  }
  return 0;
}