Coloring

Given an unrooted tree with $n$ nodes and $m$ operations, there are two types of operations: 1. Paint all nodes on the path between node $a$ and node $b$ with color $c$. 2. Query the number of color segments on the path between node $a$ and node $b$ (consecutive nodes with the same color are considered a single segment). For example, "112221" consists of 3 segments: "11", "222", and "1".

Please write a program to perform these $m$ operations in order.

Input

The first line contains two integers $n$ and $m$, representing the number of nodes and the number of operations, respectively. The second line contains $n$ positive integers representing the initial colors of the $n$ nodes. The next $n-1$ lines each contain two integers $x$ and $y$, representing an undirected edge between $x$ and $y$. The next $m$ lines each describe an operation: - "C a b c" represents a coloring operation, painting all nodes on the path between node $a$ and node $b$ (including $a$ and $b$) with color $c$. - "Q a b" represents a query operation, querying the number of color segments on the path between node $a$ and node $b$ (including $a$ and $b$).

Output

For each query operation, output the answer on a single line.

Constraints

For test cases 7, 8, 9, and 10, the tree is generated as follows: Randomly generate a permutation $p$ of $1 \sim n$, and set $p_1$ as the root. For $2 \le i \le n$, the parent of $p_i$ is $p_{\text{random}(1, i-1)}$, where $\text{random}(a, b)$ returns an element $x \in \{a, \dots, b\}$ with equal probability. Then, all edges are shuffled before being provided as input to your program.

Note

You are not allowed to use compiler flags to change the stack size. Please try to avoid using recursion to prevent stack overflow.

Examples

Input 1

6 5
2 2 1 2 1 1
1 2
1 3
2 4
2 5
2 6
Q 3 5
C 2 1 1
Q 3 5
C 5 1 2
Q 3 5

Output 1

3
1
1