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.
// practice with rainboy
import java.io.*;
import java.util.*;

public class CF601D extends PrintWriter {
	CF601D() { super(System.out, true); }
	Scanner sc = new Scanner(System.in);
	public static void main(String[] $) {
		CF601D o = new CF601D(); o.main(); o.flush();
	}

	Random rand = new Random();
	static final int MD = 0x7fffffff;
	int X = rand.nextInt(MD - 26) + 26;
	int Y = rand.nextInt(MD - 26) + 26;
	int[] next, jj; int $ = 1;
	int link(int l, int j) {
		next[$] = l; jj[$] = j;
		return $++;
	}
	int[] ao, cc; byte[] ss;
	int[] ll, rr; int time; long[] key;
	Integer[] ii; int[] pp;
	int[] tr;
	void init(int n, int m) {
		next = new int[1 + m * 2]; jj = new int[1 + m * 2];
		ao = new int[n];
		cc = new int[n];
		ll = new int[n]; rr = new int[n]; key = new long[n];
		ii = new Integer[n]; for (int i = 0; i < n; i++) ii[i] = i;
		pp = new int[n];
		tr = new int[n];
	}
	void update(int i, int n, int x) {
		while (i < n) {
			tr[i] += x;
			i |= i + 1;
		}
	}
	int query(int i) {
		int x = 0;
		while (i >= 0) {
			x += tr[i];
			i &= i + 1; i--;
		}
		return x;
	}
	void dfs(int p, int i, int x, int y) {
		x = (int) (((long) x * X + ss[i]) % MD);
		y = (int) (((long) y * Y + ss[i]) % MD);
		ll[i] = time++;
		key[ll[i]] = (long) x * MD + y;
		for (int l = ao[i]; l != 0; l = next[l]) {
			int j = jj[l];
			if (j != p)
				dfs(i, j, x, y);
		}
		rr[i] = time;
	}
	void main() {
		int n = sc.nextInt();
		init(n, n - 1);
		for (int i = 0; i < n; i++)
			cc[i] = sc.nextInt();
		ss = sc.next().getBytes();
		for (int h = 0; h < n - 1; h++) {
			int i = sc.nextInt() - 1;
			int j = sc.nextInt() - 1;
			ao[i] = link(ao[i], j);
			ao[j] = link(ao[j], i);
		}
		dfs(-1, 0, 0, 0);
		Arrays.sort(ii, (i, j) -> key[i] == key[j] ? i - j : key[i] < key[j] ? -1 : 1);
		for (int i = 0; i < n; i++)
			pp[ii[i]] = i == 0 || key[ii[i - 1]] != key[ii[i]] ? -1 : ii[i - 1];
		Arrays.sort(ii, (i, j) -> rr[i] - rr[j]);
		int c_ = -1, k = 0;
		for (int i = 0, r_ = 0; i < n; i++) {
			int i_ = ii[i], l = ll[i_], r = rr[i_];
			while (r_ < r) {
				if (pp[r_] != -1)
					update(pp[r_], n, -1);
				update(r_, n, 1);
				r_++;
			}
			cc[i_] += query(r - 1) - query(l - 1);
			if (c_ < cc[i_]) {
				c_ = cc[i_];
				k = 1;
			} else if (c_ == cc[i_])
				k++;
		}
		println(c_);
		println(k);
	}
}
