题目描述

原题来自：SDOI 2011

给定一棵有 $\red{n }$个节点的无根树和 $\red{m }$个操作，操作共两类。

$\red{1}$. 将节点$\red{ a }$到节点$\red{ b}$ 路径上的所有节点都染上颜色；

$\red{2}$. 询问节点 $\red{a }$到节点 $\red{b}$ 路径上的颜色段数量，连续相同颜色的认为是同一段，例如 112221 由三段组成：11 、 222、1。

请你写一个程序依次完成操作。

输入格式

第一行包括两个整数$\red{ n,m}$，表示节点数和操作数；

第二行包含$\red{ n }$个正整数表示 $\red{n }$个节点的初始颜色；

接下来若干行包含两个整数$\red{ x}$ 和$\red{ y}$，表示 $\red{x}$ 和 $\red{y}$ 之间有一条无向边；

接下来若干行每行描述一个操作：

• C a b c 表示这是一个染色操作，把节点 $\red{a }$到节点$\red{ b}$ 路径上所有点（包括$\red{ a }$和 $\red{b}$）染上颜色；
• Q a b 表示这是一个询问操作，把节点$\red{ a }$到节点$\red{ b}$ 路径上（包括$\red{ a}$ 和$\red{ b}$）的颜色段数量。

输出格式

对于每个询问操作，输出一行询问结果。

样例

输入样例

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

提示

对于 $\red{100\%}$ 的数据，$\red{N,M \le 10^5}$， 所有颜色$\red{ C}$ 为整数且在$\red{ [0,10^9]}$ 之间。