409025 - 染色

给定一棵 n 个结点的无根树,共有 m 个操作,操作分为两种: 1.将结点 a 到结点 b 的路径上的所有点(包括 a 和 b)都染成颜色 c。 2.询问结点 a 到结点 b 的路径上的颜色段数量。 颜色段的定义是极长的连续相同颜色被认为是一段。例如 112221 由三段组成:11、222、1。

Input

输入的第 1 行是用空格隔开的两个整数,分别代表树的结点个数 n 和操作个数 m。 第 2 行有 n 个用空格隔开的整数,第 i 个整数 wi 代表结点 i 的初始颜色。 第 3 到第 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 路径上的颜色段数量。

Output

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

Examples

Input

 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

Output

3
1
2

Hint

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

时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题