Problem: Misha has a tree with characters written on the vertices. He can choose two vertices s and t of this tree and write down characters of vertices lying on a path from s to t. We'll say that such string corresponds to pair (s, t).

Misha has m queries of type: you are given 4 vertices a, b, c, d; you need to find the largest common prefix of the strings that correspond to pairs (a, b) and (c, d). Your task is to help him.

Input

The first line contains integer n (1 ≤ n ≤ 300 000) — the number of vertices in the tree.

Next follows a line consisting of n small English letters. The i-th character of the string corresponds to the character written on the i-th vertex. 

Next n - 1 lines contain information about edges. An edge is defined by a pair of integers u, v (1 ≤ u, v ≤ n, u ≠ v), separated by spaces.

The next line contains integer m (1 ≤ m ≤ 1 000 000) — the number of queries.

Next m lines contain information about queries. A query is defined by four integers a, b, c, d (1 ≤ a, b, c, d ≤ n), separated by spaces.

Output

For each query print the length of the largest common prefix on a separate line.

Examples

Input

6
bbbabb
2 1
3 2
4 3
5 2
6 5
6
2 5 3 1
1 5 2 3
5 6 5 6
6 3 4 1
6 2 3 4
2 2 4 5


Output

2
2
2
0
1
0

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int INF = 2e9;
const long long LINF = 2e16;
const int magic = 348;
const int MOD = 998244353;
const double eps = 1e-10;
const double pi = acos(-1);
template <typename T>
inline void Get(T &first) {
  bool f;
  char ch;
  T res;
  while (!isdigit(ch = getchar()) && ch != '-') {
  }
  if (ch == '-')
    f = false, res = 0;
  else
    f = true, res = ch - '0';
  while (isdigit(ch = getchar())) res = res * 10 + ch - '0';
  first = (f ? res : (-res));
}
template <typename T1, typename... T2>
inline void Get(T1 &first, T2 &...second) {
  Get(first);
  Get(second...);
}
template <typename T>
inline void check_max(T &first, T second) {
  first = (first > second ? first : second);
}
template <typename T>
inline void check_min(T &first, T second) {
  first = (first < second ? first : second);
}
template <typename T>
inline T add(T first) {
  if (first >= MOD) first -= MOD;
  return first;
}
template <typename T>
inline T sub(T first) {
  if (first < 0) first += MOD;
  return first;
}
template <typename T>
inline void Add(T &first, T second) {
  first = add(first + second);
}
template <typename T>
inline void Sub(T &first, T second) {
  first = sub(first - second);
}
template <typename T>
inline T mul(T first, T second) {
  return 1ll * first * second % MOD;
}
template <typename T>
inline T Mul(T &first, T second) {
  first = mul(first, second);
}
inline int quick_pow(int first, int second) {
  int res = 1;
  while (second) {
    if (second & 1) res = 1ll * res * first % MOD;
    first = 1ll * first * first % MOD;
    second >>= 1;
  }
  return res;
}
const int MAXN = 3e5;
int n, q;
char s[MAXN + 48];
int anc[MAXN + 48][21], son[MAXN + 48], level[MAXN + 48], depth[MAXN + 48];
int top[MAXN + 48], Len[MAXN + 48];
vector<int> down[MAXN + 48], up[MAXN + 48];
int hbit[MAXN + 48];
int head[MAXN + 48], to[MAXN * 2 + 48], nxt[MAXN * 2 + 48], tot;
inline void addedge(int s, int t) {
  to[++tot] = t;
  nxt[tot] = head[s];
  head[s] = tot;
}
const int p = 41;
int hsh1[MAXN + 48], hsh2[MAXN + 48], pw[MAXN + 48], ipw[MAXN + 48];
inline void dfs(int cur, int father) {
  hsh1[cur] = add(mul(hsh1[father], p) + s[cur] - 'a' + 1);
  depth[cur] = depth[father] + 1;
  hsh2[cur] = add(hsh2[father] + mul(pw[depth[cur] - 1], s[cur] - 'a' + 1));
  anc[cur][0] = father;
  for (register int i = int(1); i <= int(20); i++)
    anc[cur][i] = anc[anc[cur][i - 1]][i - 1];
  son[cur] = 0;
  level[cur] = depth[cur];
  for (register int i = head[cur]; i; i = nxt[i]) {
    int second = to[i];
    if (second != father) {
      dfs(second, cur);
      if (!son[cur] || level[cur] < level[second])
        son[cur] = second, level[cur] = level[second];
    }
  }
}
inline void dfs2(int cur, int tp) {
  top[cur] = tp;
  down[tp].push_back(cur);
  Len[tp] = depth[cur] - depth[tp] + 1;
  if (son[cur]) dfs2(son[cur], tp);
  for (register int i = head[cur]; i; i = nxt[i]) {
    int second = to[i];
    if (second != anc[cur][0] && second != son[cur]) dfs2(second, second);
  }
}
inline void getUp() {
  for (register int i = int(1); i <= int(n); i++)
    if (top[i] == i) {
      int L = Len[i], tmp = i;
      while (L && tmp != 1) {
        tmp = anc[tmp][0];
        up[i].push_back(tmp);
        L--;
      }
    }
  int prod = 262144, pw = 18;
  for (register int i = int(n); i >= int(1); i--) {
    while (prod > i) prod >>= 1, pw--;
    hbit[i] = pw;
  }
}
inline int query_anc(int first, int k) {
  assert(k <= depth[first] - 1);
  if (k == 0) return first;
  int second = top[anc[first][hbit[k]]];
  assert(Len[second] >= k - (1 << hbit[k]));
  assert(second);
  if (depth[first] - depth[second] < k)
    return up[second][k - (depth[first] - depth[second]) - 1];
  else {
    assert(depth[first] - depth[second] - k <= int(down[second].size()) - 1);
    return down[second][depth[first] - depth[second] - k];
  }
}
inline int getlca(int u, int v) {
  if (depth[u] < depth[v]) swap(u, v);
  for (register int i = int(20); i >= int(0); i--)
    if (depth[anc[u][i]] >= depth[v]) u = anc[u][i];
  if (u == v) return u;
  for (register int i = int(20); i >= int(0); i--)
    if (anc[u][i] != anc[v][i]) u = anc[u][i], v = anc[v][i];
  return anc[u][0];
}
inline int query_hash1(int first, int second) {
  int len = depth[second] - depth[first] + 1;
  return sub(hsh1[second] - mul(hsh1[anc[first][0]], pw[len]));
}
inline int query_hash2(int first, int second) {
  int len = depth[second] - 1;
  return mul(sub(hsh2[first] - hsh2[anc[second][0]]), ipw[len]);
}
inline int calc_hash(int first, int second, int LCA, int len) {
  int half = depth[first] - depth[LCA] + 1;
  if (len <= half) return query_hash2(first, query_anc(first, len - 1));
  int hsh1 = query_hash2(first, LCA);
  len -= half;
  int tmp = depth[second] - depth[LCA], X = query_anc(second, tmp - 1),
      Y = query_anc(second, tmp - len);
  unsigned long long hsh2 = query_hash1(X, Y);
  len = depth[Y] - depth[X] + 1;
  return add(mul(hsh1, pw[len]) + hsh2);
}
int main() {
  Get(n);
  scanf("%s", s + 1);
  int first, second, x1, y1;
  for (register int i = int(1); i <= int(n - 1); i++)
    Get(first, second), addedge(first, second), addedge(second, first);
  pw[0] = 1;
  for (register int i = int(1); i <= int(n); i++) pw[i] = mul(pw[i - 1], p);
  ipw[n] = quick_pow(pw[n], MOD - 2);
  for (register int i = int(n - 1); i >= int(0); i--)
    ipw[i] = mul(ipw[i + 1], p);
  dfs(1, 0);
  dfs2(1, 1);
  getUp();
  Get(q);
  while (q--) {
    Get(first, second, x1, y1);
    int LCA1 = getlca(first, second), LCA2 = getlca(x1, y1);
    if (depth[first] + depth[second] - depth[LCA1] * 2 >
        depth[x1] + depth[y1] - depth[LCA2] * 2)
      swap(first, x1), swap(second, y1), swap(LCA1, LCA2);
    int ans = 0, l = 1, r = depth[first] + depth[second] - depth[LCA1] * 2 + 1,
        mid;
    while (l <= r) {
      mid = (l + r) >> 1;
      int hsh1 = calc_hash(first, second, LCA1, mid),
          hsh2 = calc_hash(x1, y1, LCA2, mid);
      if (hsh1 == hsh2)
        ans = mid, l = mid + 1;
      else
        r = mid - 1;
    }
    printf("%d\n", ans);
  }
  return 0;
}