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

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

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

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

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

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

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

每行首先有一个字符 op，代表本次操作的类型。

• 若 op 为 C，则代表本次操作是一次染色操作，在一个空格后有三个用空格隔开的整数 a,b,c，代表将 a 到 b 的路径上所有点都染成颜色 c。
• 若 op 为 Q，则代表本次操作是一次查询操作，在一个空格后有两个用空格隔开的整数 a,b，表示查询 a 到 b 路径上的颜色段数量。

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

对于每次查询操作，输出一行一个整数代表答案。