题目描述

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

1. 将节点a到节点b路径上的所有节点都染上颜色；
2. 询问节点a到节点b路径上的颜色段数量，连续相同颜色的认为是同一段，例如112221由三段组成：11、222、1。

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

输入描述

第一行包括两个整数n,m，表示节点数和操作数； 第二行包含n个正整数表示n个节点的初始颜色； 接下来若干行包含两个整数x和y，表示x和y之间有一条无向边； 接下来若干行每行描述一个操作： C a b c表示这是一个染色操作，把节点a到节点b路径上所有点（包括a和b）染上颜色； Q a b表示这是一个询问操作，把节点a到节点b路径上（包括a和b）的颜色段数量。

输出描述

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

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

备注

对于$100 \%$的数据，$N,M \le10^5$，所有颜色C为整数且在$[0,10^9]$之间。