题目描述

给定一棵有 𝑛 个节点的无根树和 𝑚 个操作，操作共两类。

1、将节点 𝑎 到节点 𝑏 路径上的所有节点都染上颜色；

2、询问节点 𝑎 到节点 𝑏 路径上的颜色段数量，连续相同颜色的认为是同一段，例如 112221由三段组成：11、 222、1。

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

输入格式

第一行包括两个整数 𝑛,𝑚，表示节点数和操作数；

第二行包含 𝑛 个正整数表示𝑛 个节点的初始颜色；

接下来若干行包含两个整数 𝑥 和 𝑦，表示 𝑥 和 𝑦 之间有一条无向边；

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

1、𝐶 𝑎 𝑏 𝑐 表示这是一个染色操作，把节点 𝑎 到节点 𝑏 路径上所有点（包括 𝑎 和 𝑏）染上颜色；

2、𝑄 𝑎 𝑏 表示这是一个询问操作，把节点𝑎 到节点𝑏 路径上（包括 𝑎 和 𝑏）的颜色段数量。。

输出格式

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

样例

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

提示

对于 $100\%$ 的数据，$N,Q \leq10^5,C \leq10^5$

数据保证对所有 QS 和 QM 事件，起点和终点城市的信仰相同；在任意时刻，城市的评级总是不大于 $10^4$ 的正整数，且宗教值不大于 $C$。