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 k^{th} letter (1 ≤ k ≤ N) is attached to the k^{th} 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 ≤ 10**^{5}- for each query,
**1 ≤ x, y ≤ the current number of nodes**, and**x ≠ y**

## Sample

Input | Output |
---|---|

3 10dga 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 | 24 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 **i ^{th}** bit is

**1**if the

**i**letter appears an odd number of times, and

^{th}**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).