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>
const int maxp = 1000010;
unsigned long long pp1[maxp], pp2[maxp];
struct S {
  unsigned hash1, rhash1;
  unsigned hash2, rhash2;
  int length;
  S() : hash1(0), rhash1(0), hash2(0), rhash2(0), length(0) {}
  S(char c) : hash1(c), rhash1(c), hash2(c), rhash2(c), length(1) {}
  S(unsigned hash1, unsigned rhash1, unsigned hash2, unsigned rhash2,
    int length)
      : hash1(hash1),
        rhash1(rhash1),
        hash2(hash2),
        rhash2(rhash2),
        length(length) {}
  S operator+(const S &b) const {
    return S((hash1 * pp1[b.length] + b.hash1) % 1000000021,
             (b.rhash1 * pp1[length] + rhash1) % 1000000021,
             (hash2 * pp2[b.length] + b.hash2) % 1000000093,
             (b.rhash2 * pp2[length] + rhash2) % 1000000093, length + b.length);
  }
  S reverse() const { return S(rhash1, hash1, rhash2, hash2, length); }
  bool operator==(const S &b) const {
    return length == b.length && hash1 == b.hash1 && hash2 == b.hash2;
  }
  bool operator!=(const S &b) const {
    return length != b.length || hash1 != b.hash1 || hash2 != b.hash2;
  }
};
const int maxn = 300010;
using namespace std;
vector<int> g[maxn];
S v[maxn];
int p[maxn], h[maxn];
void dfs(int u, int pp, int hh) {
  p[u] = pp;
  h[u] = hh;
  for (int i = 0; i < (int)g[u].size(); i++) {
    if (g[u][i] == pp) continue;
    dfs(g[u][i], u, hh + 1);
  }
}
const int maxlog = 19;
int jump_p[maxn][maxlog];
S jump_s[maxn][maxlog];
int jump(int x, int d) {
  for (int i = 0; d; i++)
    if (d & (1 << i)) {
      x = jump_p[x][i];
      d &= ~(1 << i);
    }
  return x;
}
int lca(int a, int b) {
  if (h[a] > h[b]) a = jump(a, h[a] - h[b]);
  if (h[a] < h[b]) b = jump(b, h[b] - h[a]);
  if (a == b) return a;
  for (int log = maxlog - 1; log >= 0; log--) {
    if (jump_p[a][log] != jump_p[b][log])
      a = jump_p[a][log], b = jump_p[b][log];
  }
  assert(a != b);
  a = jump_p[a][0];
  b = jump_p[b][0];
  assert(a == b && a);
  return a;
}
S get(int a, int b, int x, int d) {
  int k = min(d, h[a] - h[x]);
  S res;
  for (int i = 0; k; i++)
    if (k & (1 << i)) {
      res = res + jump_s[a][i];
      a = jump_p[a][i];
      k &= ~(1 << i);
      d -= (1 << i);
    }
  assert(d >= 0);
  if (d == 0) return res;
  res = res + v[x];
  b = jump(b, h[b] - h[x] - (d - 1));
  S res2;
  k = h[b] - h[x];
  for (int i = 0; k; i++)
    if (k & (1 << i)) {
      res2 = res2 + jump_s[b][i];
      b = jump_p[b][i];
      k &= ~(1 << i);
    }
  return res + res2.reverse();
}
bool check(int a1, int b1, int x1, int a2, int b2, int x2, int d) {
  int l1 = h[a1] + h[b1] - 2 * h[x1] + 1;
  int l2 = h[a2] + h[b2] - 2 * h[x2] + 1;
  if (d > l1 || d > l2) return false;
  S s1 = get(a1, b1, x1, d);
  S s2 = get(a2, b2, x2, d);
  assert(s1.length == d && s2.length == d);
  return s1 == s2;
}
int jump1(int a, int b, int d) {
  int res = 0;
  for (int i = 0; d; i++) {
    if ((d & (1 << i)) == 0) continue;
    d &= ~(1 << i);
    if (jump_s[a][i] == jump_s[b][i]) {
      res += (1 << i);
      a = jump_p[a][i];
      b = jump_p[b][i];
      continue;
    }
    while (i-- > 0) {
      if (jump_s[a][i] != jump_s[b][i]) continue;
      res += (1 << i);
      a = jump_p[a][i];
      b = jump_p[b][i];
    }
    break;
  }
  return res;
}
int jump2(int a, int b, int d) {
  int up[30], k = 0;
  up[k++] = a;
  for (int i = 0; (1 << i) <= d; i++) {
    if ((d & (1 << i)) == 0) continue;
    up[k] = jump_p[up[k - 1]][i];
    k++;
  }
  int res = 0;
  for (int i = 29; i >= 0; i--) {
    if ((d & (1 << i)) == 0) continue;
    --k;
    assert(k > 0);
    assert(up[k] == jump_p[up[k - 1]][i]);
    S s1 = jump_s[up[k - 1]][i];
    S s2 = jump_s[b][i];
    if (s1 == s2.reverse()) {
      res += (1 << i);
      b = jump_p[b][i];
      continue;
    }
    a = up[k - 1];
    while (i-- > 0) {
      int aa = jump_p[a][i];
      if (jump_s[b][i] == jump_s[aa][i].reverse()) {
        res += (1 << i);
        b = jump_p[b][i];
      } else {
        a = aa;
      }
    }
    break;
  }
  return res;
}
int jump3(int a, int b, int d) {
  int up1[30], up2[30], k = 0;
  up1[k] = a;
  up2[k] = b;
  k++;
  for (int i = 0; (1 << i) <= d; i++) {
    if ((d & (1 << i)) == 0) continue;
    up1[k] = jump_p[up1[k - 1]][i];
    up2[k] = jump_p[up2[k - 1]][i];
    k++;
  }
  int res = 0;
  for (int i = 29; i >= 0; i--) {
    if ((d & (1 << i)) == 0) continue;
    k--;
    assert(k > 0);
    assert(up1[k] == jump_p[up1[k - 1]][i]);
    assert(up2[k] == jump_p[up2[k - 1]][i]);
    if (jump_s[up1[k - 1]][i] == jump_s[up2[k - 1]][i]) {
      res += (1 << i);
      continue;
    }
    a = up1[k - 1];
    b = up2[k - 1];
    while (i-- > 0) {
      int aa = jump_p[a][i];
      int bb = jump_p[b][i];
      if (jump_s[aa][i] == jump_s[bb][i]) {
        res += (1 << i);
      } else {
        a = aa;
        b = bb;
      }
    }
    break;
  }
  return res;
}
int solve(int a1, int b1, int x1, int a2, int b2, int x2) {
  int d1 = min(h[a1] - h[x1], h[a2] - h[x2]);
  int j1 = jump1(a1, a2, d1);
  if (j1 != d1) return j1;
  a1 = jump(a1, d1);
  a2 = jump(a2, d1);
  if (a1 != x1) {
    swap(a1, a2);
    swap(b1, b2);
    swap(x1, x2);
  }
  assert(a1 == x1);
  int d2 = min(h[b1] - h[x1], h[a2] - h[x2]);
  int b0_a = jump(b1, h[b1] - h[x1] - d2);
  int b0 = jump(b0_a, 1);
  int j2 = jump2(b0, a2, d2);
  if (j2 != d2) return j1 + j2;
  x1 = b0_a;
  a2 = jump(a2, j2);
  if (a2 != x2) {
    assert(x1 == b1);
    b2 = x2 = a2;
  }
  int d3 = min(h[b1] - h[x1] + 1, h[b2] - h[x2] + 1);
  b1 = jump(b1, h[b1] - h[x1] + 1 - d3);
  b2 = jump(b2, h[b2] - h[x2] + 1 - d3);
  int j3 = jump3(b1, b2, d3);
  return j1 + j2 + j3;
}
int main() {
  pp1[0] = pp2[0] = 1;
  for (int i = 0; i < maxp - 1; i++) {
    pp1[i + 1] = (pp1[i] * 239017) % 1000000021;
    pp2[i + 1] = (pp2[i] * 301703) % 1000000093;
  }
  int n;
  assert(scanf("%d", &n) == 1);
  for (int i = 1; i <= n; i++) {
    char c;
    assert(scanf(" %c", &c) == 1);
    v[i] = S(c);
  }
  for (int i = 1; i < n; i++) {
    int a, b;
    assert(scanf("%d%d", &a, &b) == 2);
    g[a].push_back(b);
    g[b].push_back(a);
  }
  dfs(1, 0, 0);
  p[0] = 0;
  for (int i = 1; i <= n; i++) jump_s[i][0] = v[i], jump_p[i][0] = p[i];
  for (int log = 0; log < maxlog - 1; log++)
    for (int i = 1; i <= n; i++) {
      int t = jump_p[i][log];
      jump_p[i][log + 1] = jump_p[t][log];
      jump_s[i][log + 1] = jump_s[i][log] + jump_s[t][log];
    }
  int m;
  assert(scanf("%d", &m) == 1);
  for (int i = 0; i < m; i++) {
    int a1, b1, a2, b2;
    assert(scanf("%d%d%d%d", &a1, &b1, &a2, &b2) == 4);
    int x1 = lca(a1, b1);
    int x2 = lca(a2, b2);
    int res = solve(a1, b1, x1, a2, b2, x2);
    printf("%d\n", res);
  }
  return 0;
}