题目描述

给定一棵 $n$ 个节点的无根树，共有 $m$ 个操作，操作分为两种：

1. 将节点 $a$ 到节点 $b$ 的路径上的所有点（包括 $a$ 和 $b$）都染成颜色 $c$；
2. 询问节点 $a$ 到节点 $b$ 的路径上的颜色段数量。

颜色段的定义是极长的连续相同颜色被认为是一段。例如 112221 由三段组成：11、222、1。

输入格式

输入的第一行是用空格隔开的两个整数，分别代表树的节点个数 $n$ 和操作个数 $m$。

第二行有 $n$ 个用空格隔开的整数，第 $i$ 个整数 $w_i$ 代表结点 $i$ 的初始颜色。

第 $3$ 到第 $(n+1)$ 行，每行两个用空格隔开的整数 $u,v$，代表树上存在一条连接节点 $u$ 和节点 $v$ 的边。

第 $(n+2)$ 到第 $(n+m+1)$ 行，每行描述一个操作，其格式为：

• 若 $op$ 为 C，则后接三个整数 $a,b,c$，表示将 $a$ 到 $b$ 的路径上所有点都染成颜色 $c$；
• 若 $op$ 为 Q，则后接两个整数 $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

样例解释

如上所述。

数据范围与提示

• 对于 $100\%$ 的数据，$1 \le n,m \le 10^5$；
• $1 \le w_i,c \le 10^9$；
• $1 \le a,b,u,v \le n$；
• $op$ 一定为 C 或 Q；
• 保证给出的图是一棵树。