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;
static struct FastInput {
  static constexpr int BUF_SIZE = 1 << 20;
  char buf[BUF_SIZE];
  size_t chars_read = 0;
  size_t buf_pos = 0;
  FILE *in = stdin;
  char cur = 0;
  inline char get_char() {
    if (buf_pos >= chars_read) {
      chars_read = fread(buf, 1, BUF_SIZE, in);
      buf_pos = 0;
      buf[0] = (chars_read == 0 ? -1 : buf[0]);
    }
    return cur = buf[buf_pos++];
  }
  inline void tie(int) {}
  inline explicit operator bool() { return cur != -1; }
  inline static bool is_blank(char c) { return c <= ' '; }
  inline bool skip_blanks() {
    while (is_blank(cur) && cur != -1) {
      get_char();
    }
    return cur != -1;
  }
  inline FastInput &operator>>(char &c) {
    skip_blanks();
    c = cur;
    return *this;
  }
  inline FastInput &operator>>(string &s) {
    if (skip_blanks()) {
      s.clear();
      do {
        s += cur;
      } while (!is_blank(get_char()));
    }
    return *this;
  }
  template <typename T>
  inline FastInput &read_integer(T &n) {
    n = 0;
    if (skip_blanks()) {
      int sign = +1;
      if (cur == '-') {
        sign = -1;
        get_char();
      }
      do {
        n += n + (n << 3) + cur - '0';
      } while (!is_blank(get_char()));
      n *= sign;
    }
    return *this;
  }
  template <typename T>
  inline typename enable_if<is_integral<T>::value, FastInput &>::type
  operator>>(T &n) {
    return read_integer(n);
  }
  inline FastInput &operator>>(__int128 &n) { return read_integer(n); }
  template <typename T>
  inline typename enable_if<is_floating_point<T>::value, FastInput &>::type
  operator>>(T &n) {
    n = 0;
    if (skip_blanks()) {
      string s;
      (*this) >> s;
      sscanf(s.c_str(), "%lf", &n);
    }
    return *this;
  }
} fast_input;
static struct FastOutput {
  static constexpr int BUF_SIZE = 1 << 20;
  char buf[BUF_SIZE];
  size_t buf_pos = 0;
  static constexpr int TMP_SIZE = 1 << 20;
  char tmp[TMP_SIZE];
  FILE *out = stdout;
  inline void put_char(char c) {
    buf[buf_pos++] = c;
    if (buf_pos == BUF_SIZE) {
      fwrite(buf, 1, buf_pos, out);
      buf_pos = 0;
    }
  }
  ~FastOutput() { fwrite(buf, 1, buf_pos, out); }
  inline FastOutput &operator<<(char c) {
    put_char(c);
    return *this;
  }
  inline FastOutput &operator<<(const char *s) {
    while (*s) {
      put_char(*s++);
    }
    return *this;
  }
  inline FastOutput &operator<<(const string &s) {
    for (int i = 0; i < (int)s.size(); i++) {
      put_char(s[i]);
    }
    return *this;
  }
  template <typename T>
  inline char *integer_to_string(T n) {
    char *p = tmp + TMP_SIZE - 1;
    if (n == 0) {
      *--p = '0';
    } else {
      bool is_negative = false;
      if (n < 0) {
        is_negative = true;
        n = -n;
      }
      while (n > 0) {
        *--p = (char)('0' + n % 10);
        n /= 10;
      }
      if (is_negative) {
        *--p = '-';
      }
    }
    return p;
  }
  template <typename T>
  inline typename enable_if<is_integral<T>::value, char *>::type stringify(
      T n) {
    return integer_to_string(n);
  }
  inline char *stringify(__int128 n) { return integer_to_string(n); }
  template <typename T>
  inline typename enable_if<is_floating_point<T>::value, char *>::type
  stringify(T n) {
    sprintf(tmp, "%.17f", n);
    return tmp;
  }
  template <typename T>
  inline FastOutput &operator<<(const T &n) {
    auto p = stringify(n);
    for (; *p != 0; p++) {
      put_char(*p);
    }
    return *this;
  }
} fast_output;
int start_time;
const int _ = 3e5 + 5;
using Int = long long;
template <unsigned M_>
struct ModInt {
  static constexpr unsigned M = M_;
  unsigned x;
  constexpr ModInt() : x(0) {}
  constexpr ModInt(unsigned x_) : x(x_ % M) {}
  constexpr ModInt(unsigned long long x_) : x(x_ % M) {}
  constexpr ModInt(int x_)
      : x(((x_ %= static_cast<int>(M)) < 0) ? (x_ + static_cast<int>(M)) : x_) {
  }
  constexpr ModInt(long long x_)
      : x(((x_ %= static_cast<long long>(M)) < 0)
              ? (x_ + static_cast<long long>(M))
              : x_) {}
  ModInt &operator+=(const ModInt &a) {
    x = ((x += a.x) >= M) ? (x - M) : x;
    return *this;
  }
  ModInt &operator-=(const ModInt &a) {
    x = ((x -= a.x) >= M) ? (x + M) : x;
    return *this;
  }
  ModInt &operator*=(const ModInt &a) {
    x = (static_cast<unsigned long long>(x) * a.x) % M;
    return *this;
  }
  ModInt &operator/=(const ModInt &a) { return (*this *= a.inv()); }
  ModInt pow(long long e) const {
    if (e < 0) return inv().pow(-e);
    ModInt a = *this, b = 1;
    for (; e; e >>= 1) {
      if (e & 1) b *= a;
      a *= a;
    }
    return b;
  }
  ModInt inv() const {
    unsigned a = M, b = x;
    int y = 0, z = 1;
    for (; b;) {
      const unsigned q = a / b;
      const unsigned c = a - q * b;
      a = b;
      b = c;
      const int w = y - static_cast<int>(q) * z;
      y = z;
      z = w;
    }
    assert(a == 1);
    return ModInt(y);
  }
  ModInt operator+() const { return *this; }
  ModInt operator-() const {
    ModInt a;
    a.x = x ? (M - x) : 0;
    return a;
  }
  ModInt operator+(const ModInt &a) const { return (ModInt(*this) += a); }
  ModInt operator-(const ModInt &a) const { return (ModInt(*this) -= a); }
  ModInt operator*(const ModInt &a) const { return (ModInt(*this) *= a); }
  ModInt operator/(const ModInt &a) const { return (ModInt(*this) /= a); }
  template <class T>
  friend ModInt operator+(T a, const ModInt &b) {
    return (ModInt(a) += b);
  }
  template <class T>
  friend ModInt operator-(T a, const ModInt &b) {
    return (ModInt(a) -= b);
  }
  template <class T>
  friend ModInt operator*(T a, const ModInt &b) {
    return (ModInt(a) *= b);
  }
  template <class T>
  friend ModInt operator/(T a, const ModInt &b) {
    return (ModInt(a) /= b);
  }
  explicit operator bool() const { return x; }
  bool operator==(const ModInt &a) const { return (x == a.x); }
  bool operator!=(const ModInt &a) const { return (x != a.x); }
  friend std::ostream &operator<<(std::ostream &os, const ModInt &a) {
    return os << a.x;
  }
};
constexpr unsigned MO = 100000000 + 7;
using Mint = ModInt<MO>;
const Mint x = 19260817;
const Mint ix = Mint(1) / x;
int top[_], dep[_];
vector<int> lik[_];
vector<int> hlik[_];
int son[_], fa[_], siz[_], id[_];
int n;
string s;
Mint w[_], iw[_], val[_];
Mint h[_][2];
int root;
void dfs(int u) {
  siz[u] = 1, son[u] = u;
  int m = 1;
  for (auto v : lik[u]) {
    if (v != fa[u]) {
      fa[v] = u;
      dep[v] = dep[u] + 1;
      dfs(v);
      siz[u] += siz[v];
      if (siz[v] >= m) {
        m = siz[v];
        son[u] = v;
      }
    }
  }
  return;
}
void dfss(int u, int Top) {
  top[u] = Top;
  if (top[u] == u)
    h[u][0] = h[u][1] = val[u];
  else {
    h[u][0] = x * h[fa[u]][0] + val[u];
    h[u][1] = w[dep[u] - dep[top[u]]] * val[u] + h[fa[u]][1];
  }
  for (auto v : lik[u]) {
    if (v != fa[u]) {
      if (v == son[u])
        dfss(v, Top);
      else
        dfss(v, v);
    }
  }
  return;
}
int lca(int u, int v) {
  while (top[u] != top[v]) {
    if (dep[top[u]] > dep[top[v]])
      u = fa[top[u]];
    else
      v = fa[top[v]];
  }
  return dep[u] > dep[v] ? v : u;
}
void main_init() {
  w[0] = 1, iw[0] = 1;
  for (long long i = (1); i <= (3e5 + 1); ++i)
    w[i] = w[i - 1] * x, iw[i] = iw[i - 1] * ix;
  return;
}
void test_init() { return; }
void solve() {
  srand(start_time);
  fast_input >> n;
  root = rand() % n;
  root++;
  fast_input >> s;
  for (long long i = (0); i <= (n - 1); ++i) val[i + 1] = s[i] - 'a' + 1;
  for (long long i = (1); i <= (n - 1); ++i) {
    int u, v;
    fast_input >> u >> v;
    lik[u].push_back(v);
    lik[v].push_back(u);
  }
  dfs(root);
  dfss(root, root);
  for (long long i = (1); i <= (n); ++i)
    if (top[i] == i) {
      int now = i;
      while (1) {
        id[now] = hlik[i].size();
        hlik[i].push_back(now);
        if (son[now] == now) break;
        now = son[now];
      }
    }
  int q;
  fast_input >> q;
  while (q--) {
    int u1, v1, u2, v2;
    fast_input >> u1 >> v1 >> u2 >> v2;
    int lca1 = lca(u1, v1), lca2 = lca(u2, v2), tu, tv, las;
    Mint hlas;
    vector<pair<int, int> > U1, V1, U2, V2;
    vector<int> d1, d2;
    vector<Mint> hm1, hm2;
    las = 0;
    hlas = 0;
    tu = u1;
    while (top[tu] != top[lca1]) {
      U1.emplace_back(tu, top[tu]);
      tu = fa[top[tu]];
    }
    tv = v1;
    while (top[tv] != top[lca1]) {
      V1.emplace_back(tv, top[tv]);
      tv = fa[top[tv]];
    }
    if (tv != lca1)
      V1.emplace_back(tv, lca1);
    else
      U1.emplace_back(tu, lca1);
    reverse((V1).begin(), (V1).end());
    for (auto p : U1) {
      hm1.push_back(hlas);
      d1.push_back(las);
      hlas += w[las] * (h[p.first][0] - w[dep[p.first] - dep[p.second]] *
                                            (h[p.second][0] - val[p.second]));
      las += dep[p.first] - dep[p.second] + 1;
    }
    for (auto p : V1) {
      hm1.push_back(hlas);
      d1.push_back(las);
      hlas += w[las] *
              (h[p.first][1] -
               (h[p.second][1] -
                val[p.second] * w[dep[p.second] - dep[top[p.second]]])) *
              iw[dep[p.second] - dep[top[p.second]]];
      las += dep[p.first] - dep[p.second] + 1;
    }
    las = 0;
    hlas = 0;
    tu = u2;
    while (top[tu] != top[lca2]) {
      U2.emplace_back(tu, top[tu]);
      tu = fa[top[tu]];
    }
    tv = v2;
    while (top[tv] != top[lca2]) {
      V2.emplace_back(tv, top[tv]);
      tv = fa[top[tv]];
    }
    if (tv != lca2)
      V2.emplace_back(tv, lca2);
    else
      U2.emplace_back(tu, lca2);
    reverse((V2).begin(), (V2).end());
    for (auto p : U2) {
      hm2.push_back(hlas);
      d2.push_back(las);
      hlas += w[las] * (h[p.first][0] - w[dep[p.first] - dep[p.second]] *
                                            (h[p.second][0] - val[p.second]));
      las += dep[p.first] - dep[p.second] + 1;
    }
    for (auto p : V2) {
      hm2.push_back(hlas);
      d2.push_back(las);
      hlas += w[las] *
              (h[p.first][1] -
               (h[p.second][1] -
                val[p.second] * w[dep[p.second] - dep[top[p.second]]])) *
              iw[dep[p.second] - dep[top[p.second]]];
      las += dep[p.first] - dep[p.second] + 1;
    }
    int l = 0, r = 1 + min(dep[u1] + dep[v1] - 2 * dep[lca1],
                           dep[u2] + dep[v2] - 2 * dep[lca2]);
    while (l < r) {
      int m = r - (r - l) / 2;
      m--;
      Mint h1, h2;
      int cnt;
      cnt = upper_bound((d1).begin(), (d1).end(), m) - d1.begin() - 1;
      if (cnt >= U1.size()) {
        int from = V1[cnt - U1.size()].second,
            to = hlik[top[from]][id[from] + m - d1[cnt]];
        h1 = hm1[cnt] +
             w[d1[cnt]] *
                 (h[to][1] -
                  (h[from][1] - val[from] * w[dep[from] - dep[top[from]]])) *
                 iw[dep[from] - dep[top[from]]];
      } else {
        int from = U1[cnt].first, to = hlik[top[from]][id[from] - m + d1[cnt]];
        h1 = hm1[cnt] + w[d1[cnt]] * (h[from][0] - w[dep[from] - dep[to]] *
                                                       (h[to][0] - val[to]));
      }
      cnt = upper_bound((d2).begin(), (d2).end(), m) - d2.begin() - 1;
      if (cnt >= U2.size()) {
        int from = V2[cnt - U2.size()].second,
            to = hlik[top[from]][id[from] + m - d2[cnt]];
        h2 = hm2[cnt] +
             w[d2[cnt]] *
                 (h[to][1] -
                  (h[from][1] - val[from] * w[dep[from] - dep[top[from]]])) *
                 iw[dep[from] - dep[top[from]]];
      } else {
        int from = U2[cnt].first, to = hlik[top[from]][id[from] - m + d2[cnt]];
        h2 = hm2[cnt] + w[d2[cnt]] * (h[from][0] - w[dep[from] - dep[to]] *
                                                       (h[to][0] - val[to]));
      }
      m++;
      if (h1 == h2)
        l = m;
      else
        r = m - 1;
    }
    fast_output << l << '\n';
  }
  return;
}
signed main() {
  ios::sync_with_stdio(false);
  fast_input.tie(0);
  start_time = clock();
  main_init();
  int T = 1;
  while (T--) {
    test_init();
    solve();
  }
  return 0;
}