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.
import java.io.*;
import java.util.*;

/**
 * Created by noureldin on 2/20/17.
 */
public class main {
    private static final int MAXN = 300*1000 + 10;
    private static ArrayList<Integer> [] G = new ArrayList[MAXN];
    private static char [] link = new char[MAXN];
    private static int [] dfs_in = new int[MAXN];
    private static int [] dfs_out = new int[MAXN];
    private static int [] ord = new int[MAXN];
    private static int [] siz = new int[MAXN];
    private static int [] pref_child = new int[MAXN];
    private static int [] depth = new int[MAXN];
    private static int n,dfs_time = 0;
    private static int [] [] pmod = new int[2][MAXN];
    private static int [] base = new int[2],mod = new int[2];
    private static int [] [] H = new int[2][MAXN];
    private static int [] P = {1000000007, 999999937, 999999929, 999999893, 999999883, 999999797, 999999761, 999999757, 999999751, 999999739};
    private static HashMap<Long,Integer> HM = new HashMap<Long,Integer>();
    private static int [] cnt = new int [MAXN];
    private static int [] lev = new int [MAXN];
    private static long [] val = new long[MAXN];

    private static void dfs(int u,int parent,int d){
        dfs_in[u] = dfs_time;
        ord[dfs_time++] = u;
        siz[u] = 1;
        pref_child[u] = -1;
        depth[u] = d;
        for(int v : G[u]) if(v != parent){
            for(int i = 0;i < 2;i++){
                long x = link[v];
                H[i][v] = (int)((H[i][u] *1L* base[i] + x)%mod[i]);
            }
            dfs(v,u,d + 1);
            siz[u] += siz[v];
            if(pref_child[u] == -1 || siz[v] > siz[pref_child[u]])
                pref_child[u] = v;
        }
        dfs_out[u] = dfs_time;
        lev[d] ++;
    }

    private static long getKey(int u){
        return H[0][u] * 1000000010L + H[1][u];
    }
    private static void dfs(int u,int parent,int d,boolean keep){
        for(int v : G[u]) if(v != pref_child[u] && v != parent) dfs(v,u,d + 1,false);
        if(pref_child[u] != -1) dfs(pref_child[u],u,d + 1,true);


        long key = getKey(u);
        if(!HM.containsKey(key)) HM.put(key,0);
        HM.put(key,HM.get(key) + 1);


        for(int v : G[u]) if(v != pref_child[u] && v != parent) {
            for (int ti = dfs_in[v]; ti < dfs_out[v]; ti++) {
                int t = ord[ti];
                key = getKey(t);
                if (!HM.containsKey(key)) HM.put(key, 0);
                HM.put(key, HM.get(key) + 1);
            }
        }
        val[u] += HM.size();

        if(!keep) {
            for (int ti = dfs_in[u]; ti < dfs_out[u]; ti++) {
                int t = ord[ti];
                key = getKey(t);
                HM.put(key, HM.get(key) - 1);
                if (HM.get(key) == 0) HM.remove(key);
            }
        }
    }
    public static void main(String[] args) throws Exception{
        IO io = new IO(null,null);
        n = io.getNextInt();
        for(int i = 1;i <= n;i++) val[i] = io.getNextInt();
        String S = io.getNext();
        for(int i = 1;i <= n;i++)
            link[i] = S.charAt(i - 1);
        for(int i = 0;i <= n;i++)
            G[i] = new ArrayList<Integer>();
        for(int i = 0;i < n - 1;i++) {
            int x = io.getNextInt(), y = io.getNextInt();
            G[x].add(y);
            G[y].add(x);
        }
        G[0].add(1);
        Random rand = new Random(System.currentTimeMillis());
        for(int i = 0;i < 2;i++){
            base[i] = (int)(Math.abs(rand.nextInt())%30 + 26);
            pmod[i][0] = 1;
            mod[i] = P.length/2 + Math.abs(rand.nextInt())%(P.length/2);
            mod[i] = P[mod[i]];
        }
        for(int i = 1;i < MAXN;i++)
            for(int j = 0;j < 2;j++)
                pmod[j][i] = (int)((pmod[j][i - 1]*1L*base[j])%mod[j]);
        dfs(0,-1,0);
        dfs(0,-1,0,true);
        long best = 0;
        int ctr = 0;
        for(int i = 1;i <= n;i++){
            if(val[i] > best) {
                best = val[i];
                ctr = 0;
            }
            ctr += (val[i] == best) ? 1 : 0;
        }
        io.println(best);
        io.println(ctr);
        io.close();
    }
}

class IO{
    private BufferedReader br;
    private StringTokenizer st;
    private PrintWriter writer;
    private String inputFile,outputFile;

    public String getNext() throws FileNotFoundException, IOException{
        while(st == null || !st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
        return st.nextToken();
    }

    public String getNextLine() throws FileNotFoundException, IOException{
        return br.readLine();
    }

    public int getNextInt() throws FileNotFoundException, IOException{
        return Integer.parseInt(getNext());
    }

    public void print(Object o) throws  IOException{
        writer.print(o.toString());
    }

    public void println(Object o) throws  IOException{
        writer.println(o.toString());
    }
    public IO(String x,String y) throws FileNotFoundException, IOException{
        inputFile = x;
        outputFile = y;
        if(x != null) br = new BufferedReader(new FileReader(inputFile));
        else br = new BufferedReader(new InputStreamReader(System.in));
        if(y != null) writer = new PrintWriter(new BufferedWriter(new FileWriter(outputFile)));
        else writer = new PrintWriter(new OutputStreamWriter(System.out));
    }

    protected void close() throws IOException{
        br.close();
        writer.close();
    }
}
