The Oddest Tree

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

InputOutput
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.
Questions?

Sponsors Gold