一组科学家分析了一个有若干蚁群居住的蚁巢。他们发现蚁巢是一个树状结构，其中每个节点代表一个蚁群居住的物理位置，每条边代表连接两个蚁群的隧道。最有趣的是，每个蚁群都有且仅有一种颜色，并且有时会改变颜色。颜色改变机制取决于给定两个蚁群 $A$ 和 $B$ 之间路径上具有某种颜色 $c$ 的最近蚁群对。两个蚁群之间的距离是连接它们的路径上的隧道数量，即连接对应节点的路径上的边数。

例如，图 A.1 (a) 展示了一个具有五个蚁群的树状结构，蚁群编号为 1 到 5，颜色分别为 1, 2, 2, 2, 1（在蚁群上方用橙色标出，按从蚁群 1 到蚁群 5 的顺序）。对于颜色 2 以及蚁群 2 和 5，路径上具有颜色 2 的最近蚁群对是 (蚁群 2, 蚁群 3)。但对于蚁群 2 和 4，具有颜色 2 的最近蚁群对是 (蚁群 3, 蚁群 4)。

假设现在蚁群 3 的当前颜色 2 变为颜色 3，如图 A.1 (b) 所示。那么在蚁群 2 和 5 之间的路径上就不存在具有颜色 2 的最近蚁群对，因为只有一个蚁群具有颜色 2。对于蚁群 2 和 4，具有颜色 2 的最近蚁群对变为 (蚁群 2, 蚁群 4)。

给定蚁群的颜色、蚁巢的树状结构以及一系列按顺序排列的更新命令（用于改变颜色）和查询命令（用于寻找最近蚁群对），请编写一个程序，针对每个查询 $(S, A, B, c)$，找出路径上具有颜色 $c$ 的两个蚁群之间的最近距离。

图 A.1 一个有五个蚁群的蚁巢。橙色数字代表蚁群颜色。

输入格式

程序应从标准输入读取数据。输入的第一行包含两个整数 $n$ 和 $q$ ($2 \le n \le 100,000$, $2 \le q \le 100,000$)，其中 $n$ 是蚁群的数量，$q$ 是更新和查询命令的数量。蚁群编号从 1 到 $n$，颜色用 $\{1, 2, \dots, n\}$ 中的整数标识。下一行包含 $n$ 个正整数，表示蚁群的颜色，顺序从蚁群 1 到蚁群 $n$。接下来的 $n-1$ 行中，第 $i$ 行包含一对整数 $a_i, b_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i$)，指定了由隧道连接的两个蚁群，这对应于树结构中的一条边。接下来的 $q$ 行中，第 $i$ 行的形式为 $(S, A, B, c)$ 或 $(S, A, c)$，其中 $S$ 是一个大写字符 'U' 或 'Q'，分别代表更新和查询。如果 $S = \text{'U'}$，则命令形式为 $(S, A, c)$，表示将蚁群 $A$ 的当前颜色更新为颜色 $c$ ($1 \le A, c \le n$)。如果 $S = \text{'Q'}$，则命令形式为 $(S, A, B, c)$，表示查询蚁群 $A$ 和蚁群 $B$ 之间路径上具有颜色 $c$ 的最近蚁群对的距离 ($1 \le A, B, c \le n$)。这些命令必须按照输入中给出的顺序执行。

输出格式

程序应写入标准输出。对于每个 $S = \text{'Q'}$ 的查询 $(S, A, B, c)$，输出一行，包含在当前蚁巢状态下，蚁群 $A$ 和 $B$ 之间路径上具有颜色 $c$ 的最近蚁群对的距离。如果它们之间不存在具有颜色 $c$ 的蚁群对，则输出 -1。

样例

样例输入 1

5 5
1 2 2 2 1
1 2
3 1
3 4
3 5
Q 2 5 2
Q 2 4 2
U 3 3
Q 2 5 2
Q 2 4 2

样例输出 1

2
1
-1
3

样例输入 2

4 6
2 1 1 1
1 2
1 3
1 4
Q 2 3 1
Q 2 4 1
Q 3 4 1
U 1 1
Q 2 3 1
Q 2 4 1

样例输出 2

2
2
2
1
1