题目描述

聪明兔喜欢树上问题。树有 $n$ 个结点，编号为 $1$ 到 $n$，根结点为 $1$。每个结点具有一个固定的正整数权值，并且有黑、白两种颜色。初始时，所有结点均为白色。

聪明兔依次执行以下两种操作：

• Modify v：将结点 $v$ 的颜色修改为黑色。一个结点可能被修改多次；重复修改后仍为黑色。
• Query v：在所有黑色结点中选择一个结点 $u$，令 $z$ 为 $u$ 与 $v$ 的最近公共祖先，要求 $z$ 的权值尽可能大，输出这个最大权值。如果还没有黑色结点，输出 $-1$。

结点的权值在整个过程中保持不变。

输入格式

从标准输入读入数据。

第一行包含两个正整数 $n,m$，分别表示树的结点数和操作总数。

第二行包含 $n$ 个正整数 $w_1,w_2,\ldots,w_n$，其中 $w_i$ 表示结点 $i$ 的固定权值。

接下来 $n-1$ 行，每行包含两个正整数 $a_i,b_i$，表示这两个结点之间有一条边。

接下来 $m$ 行，每行包含一个字符串和一个正整数 $v$，格式为 Modify v 或 Query v，含义如题目描述所示。

输出格式

输出到标准输出。

对于每个 Query 操作，每行输出一个整数，表示对应询问的答案。

7 7
4 3 5 7 6 5 2
1 4
2 1
7 5
6 2
2 5
3 4
Query 1
Modify 2
Modify 4
Query 3
Modify 2
Modify 5
Query 6

-1
7
4

数据范围

对于所有数据，$n \le 100000$，$m \le 200000$。所有权值均为正整数。每个测试点 $5$ 分。

特殊性质 A：对于编号为 $i$ 的结点（$i > 1$），其父亲结点编号在 $[1,i-1]$ 内均匀随机。

特殊性质 B：保证所有 Query 操作都在全部 Modify 操作完成之后。