A and B are playing a game.

There is a tree like structure. Each node of tree contains a lowercase alphabet and also have an index asscoiated with it. In each turn, a player tells opponent player two integers L and R.  The opponent player pick up all the alphabets lying in the shortest path from L to R and makes all possible words using all those letters and gets 1 point for every word he made which exists in dictionary. After each move, the tree is restored back to its initial condition.

You are given the tree structure, the dictionary and collection of L , R and player for each turn. Find the score of A and B after the game has finished. The score of A and B is 0 at the start of game.

 

Input : 

The first line contains \(N,K,Q\). \(N\) is the no  of vertices in the tree,\(K\) is no. of words in dictionary, \(Q\) is the number of turns made in the game.

Next line contains \(N\) space seperated letters, the \(i^{th}\) letter is the alphabet associated with \(i^{th}\) node of the tree. 

Next \(N-1\) lines contains two space seperated integers \(U\) and \(V\). This means there is an edge in the tree between U and V.

Then \(K\) lines follows, each line contains a string (word in the dictionary). All words in the dictionary are distinct.

Then \(Q\) lines follows, each contains \(P\quad L \quad R\).  L and R are the index associated with the vertices of tree. P = A means A made the words and P = B means B made the words.

 

Output :

Print two space seperated integers. Score of A and B respectively.

 

Constraints :

\(1 \le N \le 200000\)

\(1 \le K \le 50000\)

\(1 \le Q \le 50000\)

All alphabets are from small english letters.

Size of any word in dictionary is always greater than 0 and less than 11.