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. |
In order to solve this problem, we need to use the properties of binary operation XOR. More concisely, the XOR sum of N bits provides the parity of N.
In each node we will store a binary array of length SIGMA (26 - the size of the alphabet). The ith bit is 1 if the ith letter appears an odd number of times, and 0 otherwise.
Let's take two nodes x and y. Let us use the following notation:
- x(1), x(2), …, x(L1) - the array of nodes on the chain from 1 to x , where x(1) = 1 and x(L1) = x.
- y(1), y(2), …, y(L2) - analoguely.
Also, let mask[x] = info[x(1)] ^ info[x(2)] ^ … ^ info[x(L1)]. The same goes for mask[y].
Let lca = LCA(x, y) (the lowest common ancestor of x and y). There exists one pair (i, j) such that:
- 1 ≤ i ≤ L1
- 1 ≤ j ≤ L2
- x(i) = lca = y(j)
We take a number A. We know that A ^ A = 0, so:
mask[x] ^ mask[y] = XOR_SUM(x(p), i < p ≤ L1) ^ XOR_SUM(y(q), j < q ≤ L2)
lca lies on the chain from x to y, so the answer would be mask[x] ^ mask[y] ^ info[lca].
For any update, the mask can be calculated in contant time. The only problem left is finding the LCA in a changing tree.
This can be achived in O(sqrt(N)) or O(log(N)) (see: Stramosi).
