You are given a tree T with n vertices (numbered 1 through n) and a letter in each vertex. The tree is rooted at vertex 1.

Let's look at the subtree Tv of some vertex v. It is possible to read a string along each simple path starting at v and ending at some vertex in Tv (possibly v itself). Let's denote the number of distinct strings which can be read this way as <image>. 

Also, there's a number cv assigned to each vertex v. We are interested in vertices with the maximum value of <image>.

You should compute two statistics: the maximum value of <image> and the number of vertices v with the maximum <image>.

Input

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

The second line contains n space-separated integers ci (0 ≤ ci ≤ 109).

The third line contains a string s consisting of n lowercase English letters — the i-th character of this string is the letter in vertex i.

The following n - 1 lines describe the tree T. Each of them contains two space-separated integers u and v (1 ≤ u, v ≤ n) indicating an edge between vertices u and v.

It's guaranteed that the input will describe a tree.

Output

Print two lines. 

On the first line, print <image> over all 1 ≤ i ≤ n. 

On the second line, print the number of vertices v for which <image>.

Examples

Input

10
1 2 7 20 20 30 40 50 50 50
cacabbcddd
1 2
6 8
7 2
6 2
5 4
5 9
3 10
2 5
2 3


Output

51
3


Input

6
0 2 4 1 1 1
raaaba
1 2
2 3
2 4
2 5
3 6


Output

6
2

Note

In the first sample, the tree looks like this:

<image>

The sets of strings that can be read from individual vertices are:

<image>

Finally, the values of <image> are:

<image>

In the second sample, the values of <image> are (5, 4, 2, 1, 1, 1). The distinct strings read in T2 are <image>; note that <image> can be read down to vertices 3 or 4.
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 999998727899999ll, MAXN = 300001;
long long c[MAXN];
vector<long long> g[MAXN];
set<long long> s[MAXN];
string t;
bool mark[MAXN];
long long base = 101;
long long diff[MAXN];
long long ans[MAXN];
long long n;
void dsu(long long a1, long long a2) {
  set<long long>::iterator it = s[a2].begin();
  while (it != s[a2].end()) {
    s[a1].insert(*it);
    it++;
  }
  s[a2].clear();
}
int dfs(long long v, long long h) {
  long long hash = ((h * base) + (t[v - 1] - 'a' + 1)) % MOD;
  mark[v] = 1;
  vector<int> child;
  for (int i = 0; i < g[v].size(); i++) {
    long long u = g[v][i];
    if (!mark[u]) {
      child.push_back(dfs(u, hash));
    }
  }
  if (child.size() == 0) {
    diff[v] = 1;
    s[v].insert(hash);
    return v;
  } else {
    int w = 0;
    for (int i = 1; i < child.size(); i++) {
      if (s[child[i]].size() > s[child[w]].size()) {
        w = i;
      }
    }
    for (int i = 0; i < child.size(); i++) {
      if (i != w) {
        dsu(child[w], child[i]);
      }
    }
    s[child[w]].insert(hash);
    diff[v] = s[child[w]].size();
    return child[w];
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> c[i];
    ans[i] = i;
  }
  cin >> t;
  for (int i = 1; i < n; i++) {
    int u, v;
    cin >> u >> v;
    g[v].push_back(u);
    g[u].push_back(v);
  }
  dfs(1, 0);
  long long mx = 0;
  for (int i = 1; i <= n; i++) {
    mx = max(diff[i] + c[i], mx);
  }
  long long cnt = 0;
  for (int i = 1; i <= n; i++) {
    if (diff[i] + c[i] == mx) {
      cnt++;
    }
  }
  cout << mx << endl;
  cout << cnt;
  return 0;
}
