Tree Label Queries

You are given a tree with n nodes (numbered 1 through n) and n-1 directed edges. The tree is rooted at node 1. Initially, each node does not have a label (or you may assume it is unassigned).

You will be given a series of queries. There are two types of queries:

• LABEL u x: Assign the label of node u to an integer x. The labels correspond to English uppercase letters in the following way: the label x represents the letter given by the formula $$\text{letter} = \text{chr}(x + \text{ord}('A') - 1),$$ so label 1 stands for 'A', label 2 for 'B', etc.
• FREQ u C: For the subtree rooted at node u, count the number of nodes whose label equals the number corresponding to the uppercase letter C (i.e. $$x = \text{ord}(C)-\text{ord}('A')+1$$). Print the count for this query.

For each query of type FREQ output the answer on a new line.

inputFormat

The input is given via standard input and is formatted as follows:

1. An integer n representing the number of nodes.
2. n-1 lines follow, each containing two integers u and v representing an edge from node u to node v.
3. An integer Q representing the number of queries.
4. Q lines follow; each line is either:
   • LABEL u x where u is the node and x is the label value (a positive integer), or
   • FREQ u C where u is the node and C is an uppercase letter.

outputFormat

For each FREQ query, print a single integer on a new line corresponding to the count of nodes in the subtree of the given node that have the label corresponding to the given letter.

## sample

5
1 2
1 3
3 4
3 5
10
LABEL 1 1
LABEL 2 2
LABEL 3 3
LABEL 4 1
LABEL 5 2
FREQ 1 B
FREQ 3 A
FREQ 5 B
LABEL 5 1
FREQ 3 A

2
1
1
2

</p>