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;
template <class TAT>
inline void read(TAT &a) {
  static char cc;
  static bool f;
  while ((cc = getchar()) != '-' && (cc < '0' || cc > '9'))
    ;
  if (cc == '-')
    f = 1, a = 0;
  else
    f = 0, a = cc - '0';
  while ((cc = getchar()) >= '0' && cc <= '9') a = a * 10 + cc - '0';
  if (f) a = -a;
}
template <class TAT>
inline void write(TAT a) {
  static char cc[27];
  static int ct;
  if (a == 0) {
    putchar('0');
    return;
  }
  if (a < 0) {
    a = -a;
    putchar('-');
  }
  ct = 0;
  while (a) cc[++ct] = a % 10 + '0', a /= 10;
  while (ct) putchar(cc[ct--]);
}
template <class TAT>
inline void Ckmin(TAT &a, const TAT &b) {
  if (a > b) a = b;
}
template <class TAT>
inline void Ckmax(TAT &a, const TAT &b) {
  if (a < b) a = b;
}
void begin() {
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
}
void end() {
  fclose(stdin);
  fclose(stdout);
}
const int maxn = 3e5 + 115;
const int J = 47;
const int mod = 998244353;
int n, m;
char C[maxn];
struct edge {
  int to, next;
  edge() {}
  edge(int _t, int _n) : to(_t), next(_n) {}
} e[maxn * 2];
struct Seg {
  int x, len;
  bool dir;
  Seg() {}
  Seg(int _x, int _len, bool _dir) : x(_x), len(_len), dir(_dir) {}
} L1[maxn], L2[maxn], Linkout[maxn];
int l1 = 0, l2 = 0;
int head[maxn], et = -1;
int fa[maxn], size[maxn], zs[maxn], deep[maxn], top[maxn], dfn[maxn], rak[maxn],
    Index = 0, ms[maxn];
int zx[maxn * 4], fx[maxn * 4], lx[maxn * 4];
int pre[maxn], suf[maxn];
long long mi[maxn], nv[maxn];
int lkt = 0;
void Init() {
  int x, y;
  read(n);
  scanf("%s", C + 1);
  memset(head, -1, sizeof(head));
  et = -1;
  for (int i = 1; i < n; ++i) {
    read(x), read(y);
    e[++et] = edge(y, head[x]), head[x] = et;
    e[++et] = edge(x, head[y]), head[y] = et;
  }
}
void Dfs1(int p) {
  ms[p] = 0;
  zs[p] = -1;
  size[p] = 1;
  for (int i = head[p]; i != -1; i = e[i].next) {
    if (fa[p] == e[i].to) continue;
    fa[e[i].to] = p;
    deep[e[i].to] = deep[p] + 1;
    Dfs1(e[i].to);
    size[p] += size[e[i].to];
    if (size[e[i].to] > ms[p]) {
      ms[p] = size[e[i].to];
      zs[p] = e[i].to;
    }
  }
}
void Dfs2(int p, int tp) {
  top[p] = tp;
  dfn[p] = ++Index;
  rak[dfn[p]] = p;
  if (zs[p] != -1) {
    Dfs2(zs[p], tp);
  }
  for (int i = head[p]; i != -1; i = e[i].next) {
    if (fa[p] == e[i].to || e[i].to == zs[p]) continue;
    Dfs2(e[i].to, e[i].to);
  }
}
void tBuild(int l, int r, int p) {
  int mid = (l + r) / 2;
  lx[p] = r - l + 1;
  if (l == r) {
    zx[p] = fx[p] = C[rak[l]] - 'a';
    return;
  }
  tBuild(l, mid, p << 1);
  tBuild(mid + 1, r, p << 1 | 1);
  zx[p] = (zx[p << 1] * mi[lx[p << 1 | 1]] % mod + zx[p << 1 | 1]) % mod;
  fx[p] = (fx[p << 1 | 1] * mi[lx[p << 1]] % mod + fx[p << 1]) % mod;
}
int tFindZ(int l, int r, int L, int R, int p) {
  int mid = (l + r) / 2;
  if (L <= l && R >= r) {
    return zx[p];
  }
  if (L > mid)
    return tFindZ(mid + 1, r, L, R, p << 1 | 1);
  else if (R <= mid)
    return tFindZ(l, mid, L, R, p << 1);
  else
    return (tFindZ(l, mid, L, R, p << 1) * mi[R - mid] % mod +
            tFindZ(mid + 1, r, L, R, p << 1 | 1)) %
           mod;
}
int tFindF(int l, int r, int L, int R, int p) {
  int mid = (l + r) / 2;
  if (L <= l && R >= r) {
    return fx[p];
  }
  if (L > mid)
    return tFindF(mid + 1, r, L, R, p << 1 | 1);
  else if (R <= mid)
    return tFindF(l, mid, L, R, p << 1);
  else
    return (tFindF(l, mid, L, R, p << 1) +
            tFindF(mid + 1, r, L, R, p << 1 | 1) * mi[mid - L + 1] % mod) %
           mod;
}
inline long long Pow(long long x, int y) {
  long long S = 1;
  while (y) {
    if (y & 1) S = (S * x) % mod;
    x = (x * x) % mod;
    y >>= 1;
  }
  return S;
}
void Build() {
  pre[0] = 0;
  for (int i = 1; i <= n; ++i) {
    pre[i] = (pre[i - 1] + (C[rak[i]] - 'a') * mi[i - 1] % mod) % mod;
  }
  suf[n + 1] = 0;
  for (int i = n; i >= 1; --i) {
    suf[i] = (suf[i + 1] + (C[rak[i]] - 'a') * mi[n - i] % mod) % mod;
  }
}
int FindZ(int l, int r) {
  int tp;
  tp = (pre[r] - pre[l - 1] + mod) % mod;
  tp = tp * nv[l - 1] % mod;
  return tp;
}
int FindF(int l, int r) {
  int tp;
  tp = (suf[l] - suf[r + 1] + mod) % mod;
  tp = tp * nv[n - r] % mod;
  return tp;
}
inline int Gethash(int l, int r) {
  if (l < r) {
    return FindZ(l, r);
  } else {
    return FindF(r, l);
  }
}
inline void Prepare() {
  mi[0] = 1;
  for (int i = 1; i <= n; ++i) {
    mi[i] = (long long)mi[i - 1] * J % mod;
  }
  for (int i = 0; i <= n; ++i) {
    nv[i] = Pow(mi[i], mod - 2);
  }
  deep[1] = 1;
  Dfs1(1);
  Index = 0;
  Dfs2(1, 1);
  Build();
}
inline void Getline(int st, int ed) {
  static Seg Z[maxn], F[maxn];
  int zt = 0, ft = 0;
  lkt = 0;
  while (1) {
    if (top[st] == top[ed]) {
      if (deep[st] > deep[ed]) {
        Z[++zt] = Seg(ed, dfn[st] - dfn[ed] + 1, 0);
      } else {
        F[++ft] = Seg(ed, dfn[ed] - dfn[st] + 1, 1);
      }
      break;
    } else if (deep[top[st]] > deep[top[ed]]) {
      Z[++zt] = Seg(top[st], dfn[st] - dfn[top[st]] + 1, 0);
      st = fa[top[st]];
    } else {
      F[++ft] = Seg(ed, dfn[ed] - dfn[top[ed]] + 1, 1);
      ed = fa[top[ed]];
    }
  }
  lkt = 0;
  for (int i = 1; i <= zt; ++i) {
    Linkout[++lkt] = Z[i];
  }
  for (int i = ft; i >= 1; --i) {
    Linkout[++lkt] = F[i];
  }
}
inline void Getqj(const Seg &x, int l, int &a, int &b) {
  if (x.dir == 0) {
    a = dfn[x.x] + x.len - 1;
    b = a - l + 1;
  } else {
    a = dfn[x.x] - x.len + 1;
    b = a + l - 1;
  }
}
inline void Query(int s1, int t1, int s2, int t2) {
  int Ans = 0;
  Getline(s1, t1);
  l1 = lkt;
  for (int i = 1; i <= l1; ++i) L1[i] = Linkout[i];
  Getline(s2, t2);
  l2 = lkt;
  for (int i = 1; i <= l2; ++i) L2[i] = Linkout[i];
  int p1 = 1, p2 = 1, L;
  int a, b, c, d;
  int el = 0, er = 0, emid, emax;
  while (p1 <= l1 && p2 <= l2) {
    L = min(L1[p1].len, L2[p2].len);
    Getqj(L1[p1], L, a, b);
    Getqj(L2[p2], L, c, d);
    if (Gethash(a, b) == Gethash(c, d)) {
      Ans += L;
      L1[p1].len -= L;
      if (L1[p1].len == 0) ++p1;
      L2[p2].len -= L;
      if (L2[p2].len == 0) ++p2;
      continue;
    } else {
      el = 0, er = L;
      emax = 0;
      while (er > el + 1) {
        emid = (el + er) / 2;
        Getqj(L1[p1], emid, a, b);
        Getqj(L2[p2], emid, c, d);
        if (Gethash(a, b) == Gethash(c, d)) {
          el = emid;
          Ckmax(emax, emid);
        } else {
          er = emid;
        }
      }
      Ans += emax;
      break;
    }
  }
  write(Ans);
  putchar('\n');
}
void Solve() {
  int a, b, c, d;
  read(m);
  for (int i = 1; i <= m; ++i) {
    read(a), read(b), read(c), read(d);
    Query(a, b, c, d);
  }
}
int main() {
  Init();
  Prepare();
  Solve();
  return 0;
}