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 primero = 1 << 21;
const int tope = 1 << 22;
const int limite = 300001;
pair<int, int> minimo[tope];
void inserta(int pos, pair<int, int> val) {
  pos += primero;
  minimo[pos] = val;
  while (pos > 1) {
    pos /= 2;
    minimo[pos] = min(minimo[2 * pos], minimo[2 * pos + 1]);
  }
}
int minimoentre(int pos0, int pos1) {
  pos0 += primero;
  pos1 += primero;
  if (pos0 == pos1) return minimo[pos0].second;
  if (pos0 > pos1) swap(pos0, pos1);
  pair<int, int> mini = min(minimo[pos0], minimo[pos1]);
  while (pos0 + 1 < pos1) {
    if (pos0 % 2 == 0) mini = min(mini, minimo[pos0 + 1]);
    pos0 /= 2;
    if (pos1 % 2 == 1) mini = min(mini, minimo[pos1 - 1]);
    pos1 /= 2;
  }
  return mini.second;
}
int n;
int valor[limite];
vector<int> g[limite];
int profundidad[limite];
vector<int> listaprof[limite];
int posicionle[limite];
int posiciontot = 0;
long long int h1propio[limite];
long long int h1hasta[limite];
long long int h2propio[limite];
long long int h2hasta[limite];
long long int primo = 109;
long long int modulo = 1e9 + 7;
long long int expo[limite];
long long int expoinv[limite];
long long int eleva(long long int b, long long int e) {
  if (e == 0) return 1;
  if (e % 2 == 0) return eleva(b * b % modulo, e / 2);
  return b * eleva(b * b % modulo, e / 2) % modulo;
}
long long int inverso(long long int x) { return eleva(x, modulo - 2); }
int intermedio(int u, int v) {
  return minimoentre(posicionle[u], posicionle[v]);
}
int predecesor(int u, int prof) {
  int pule = posicionle[u];
  vector<int> &w = listaprof[prof];
  int inf = 0;
  int sup = int(w.size());
  while (inf + 1 < sup) {
    int med = (inf + sup) / 2;
    if (posicionle[w[med]] <= pule)
      inf = med;
    else
      sup = med;
  }
  return w[inf];
}
int distancia(int u, int v, int med) {
  return profundidad[u] - profundidad[med] + profundidad[v] - profundidad[med];
}
long long int arregla(long long int x) {
  return (x % modulo + modulo) % modulo;
}
long long int hentre(int u, int v, int med, int len) {
  if (len <= profundidad[u] - profundidad[med]) {
    int w = predecesor(u, profundidad[u] - len);
    return arregla((h2hasta[u] - (h2hasta[w] - h2propio[w])) *
                   expoinv[limite - 1 - profundidad[u]]);
  }
  int w = predecesor(
      v, profundidad[med] + (len - (profundidad[u] - profundidad[med])));
  return arregla((h2hasta[u] - (h2hasta[med] - h2propio[med])) *
                     expoinv[limite - 1 - profundidad[u]] +
                 (h1hasta[w] - h1hasta[med]) * expoinv[profundidad[med]] %
                     modulo * expo[profundidad[u] - profundidad[med]]);
}
void genera(int u, int p, int prof) {
  h1propio[u] = valor[u] * expo[prof] % modulo;
  h1hasta[u] = (h1hasta[p] + h1propio[u]) % modulo;
  h2propio[u] = valor[u] * expo[limite - 1 - prof] % modulo;
  h2hasta[u] = (h2hasta[p] + h2propio[u]) % modulo;
  profundidad[u] = prof;
  vector<int> &ar = g[u];
  listaprof[prof].push_back(u);
  posicionle[u] = posiciontot;
  inserta(posiciontot, pair<int, int>(prof, u));
  posiciontot++;
  for (int i = 0; i < int(ar.size()); i++) {
    int v = ar[i];
    if (v != p) {
      genera(v, u, prof + 1);
      inserta(posiciontot, pair<int, int>(prof, u));
      posiciontot++;
    }
  }
}
char input[1000000];
int main() {
  expo[0] = 1;
  expo[1] = primo;
  expoinv[0] = 1;
  expoinv[1] = inverso(primo);
  for (int i = 2; i < limite; i++) {
    expo[i] = (expo[i - 1] * expo[1]) % modulo;
    expoinv[i] = (expoinv[i - 1] * expoinv[1]) % modulo;
  }
  scanf("%d", &n);
  scanf("%s", input);
  for (int i = 1; i <= n; i++) valor[i] = input[i - 1] - 'a';
  for (int i = 0; i < n - 1; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    g[u].push_back(v);
    g[v].push_back(u);
  }
  genera(1, 0, 0);
  int casos;
  scanf("%d", &casos);
  for (int cas = 0; cas < casos; cas++) {
    int u1, v1, u2, v2;
    scanf("%d %d %d %d", &u1, &v1, &u2, &v2);
    int med1 = intermedio(u1, v1);
    int med2 = intermedio(u2, v2);
    int inf = 0;
    int sup = min(distancia(u1, v1, med1), distancia(u2, v2, med2)) + 1;
    if (h1propio[u1] * expoinv[profundidad[u1]] % modulo !=
        h1propio[u2] * expoinv[profundidad[u2]] % modulo) {
      printf("0\n");
      continue;
    }
    while (inf + 1 < sup) {
      int med = (inf + sup) / 2;
      if (hentre(u1, v1, med1, med) == hentre(u2, v2, med2, med))
        inf = med;
      else
        sup = med;
    }
    printf("%d\n", inf + 1);
  }
}