Let G be an undirected tree with N nodes. Each node has a lowercase English letter attached to it. You are given M operations. Each operation is either a query (type 1) or an update (type 2), provided using the following format:
- 1 x y - output the number of letters that have an odd number of occurences on the path from node x to node y.
- 2 x c - a new node is added to the tree, by attaching it to existing node x; the letter associated with it is c.
Input
The first line of input contains integers N and M.
The second line of input contains a sequence of N lowercase english characters. The kth letter (1 ≤ k ≤ N) is attached to the kth node.
The following N-1 lines contain the tree's edges.
The following M lines describe the operations, in the established format.
Output
For each query, you should output a single integer between 0 and 26, followed by a newline character.
Constraints
- 1 ≤ N, M ≤ 105
- for each query, 1 ≤ x, y ≤ the current number of nodes, and x ≠ y
Sample
| Input | Output |
|---|---|
| 3 10 dga 3 1 3 2 2 3 e 2 2 b 1 2 3 1 5 1 1 3 1 1 5 2 2 3 f 1 2 6 2 5 f 1 1 6 | 2 4 2 2 3 3 |
 | Explanation: the tree is odd. |