[SDOI2011]染色

给定一棵有 $n$ 个节点的无根树和 $m$ 个操作，操作有以下 $2$ 类：

1. 将节点 $a$ 到节点 $b$ 的路径上所有节点都染成颜色 $c$。
2. 询问节点 $a$ 到节点 $b$ 的路径上有多少个颜色段，其中连续的相同颜色被视为同一个颜色段。

例如，颜色序列 $112221$ 由 $3$ 段组成，分别为 $11$、$222$ 和 $1$。

请你编写程序，依次完成这 $m$ 个操作。

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示节点数和操作数。

第二行包含 $n$ 个正整数，表示 $n$ 个节点的初始颜色。

接下来 $n-1$ 行，每行包含两个整数 $x$ 和 $y$，表示节点 $x$ 和节点 $y$ 之间有一条无向边。

接下来 $m$ 行，每行描述一个操作：

• C a b c 表示染色操作，将节点 $a$ 到节点 $b$ 的路径上所有节点，包括 $a$ 和 $b$，都染成颜色 $c$。
• Q a b 表示询问操作，询问节点 $a$ 到节点 $b$ 的路径上，包括 $a$ 和 $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

数据范围

• $n\le10^5$；
• $m\le10^5$；
• 所有颜色 $c$ 均为整数，且满足 $0\le c\le10^9$。

来源与许可

本题为 SDOI 2011 试题「染色」，题面与测试数据整理自 BZOJ 2243。

样例 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