Description:
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 $$\operatorname{dif}(v)$$.
Also, there's a number cv assigned to each vertex v. We are interested in vertices with the maximum value of $$\mathrm{dif}(v) + c_v$$.
You should compute two statistics: the maximum value of $$\mathrm{dif}(v) + c_v$$ and the number of vertices v with the maximum $$\mathrm{dif}(v) + c_v$$.
Input Format:
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 Format:
Print two lines.
On the first line, print $$m = \max(\operatorname{dif}(i) + c_i)$$ over all 1 ≤ i ≤ n.
On the second line, print the number of vertices v for which $$m = \operatorname{dif}(v) + c_v$$.
Note:
In the first sample, the tree looks like this:
The sets of strings that can be read from individual vertices are:
Finally, the values of $$\mathrm{dif}(v) + c_v$$ are:
In the second sample, the values of $$\operatorname{dif}(1..n)$$ are (5, 4, 2, 1, 1, 1). The distinct strings read in T2 are $$a, aa, aaa, ab$$; note that $$\alpha \alpha$$ can be read down to vertices 3 or 4.