Description

Original source: SDOI 2011

Given a tree with $n$ nodes and $m$ operations, there are two types of operations:

1. Color all nodes on the path from node $a$ to node $b$ with a specified color;

2. Query the number of color segments on the path from node $a$ to node $b$, where consecutive nodes with the same color are considered as one segment. For example, 112221 consists of three segments: 11, 222, and 1.

Write a program to execute these operations sequentially.

Input Format

The first line contains two integers $n$ and $m$, representing the number of nodes and operations, respectively;

The second line contains $n$ positive integers representing the initial colors of the $n$ nodes;

The next several lines each contain two integers $x$ and $y$, indicating an undirected edge between node $x$ and node $y$;

The subsequent lines each describe an operation:

• C a b c denotes a coloring operation, coloring all nodes (including $a$ and $b$) on the path from node $a$ to node $b$ with color $c$;

• Q a b denotes a query operation, asking for the number of color segments on the path from node $a$ to node $b$ (including $a$ and $b$).

Output Format

For each query operation, output the result on a separate line.

Sample 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

3
1
2

Constraints and Hints

For $100\%$ of the data, $N,M \le 10^5$, and all colors $C$ are integers within the range $[0,10^9]$.