题目描述

一棵以 $1$ 为根的树，每个点有一个权值，一个数字从根节点出发，不断按照如下策略行动：

• 在当前点的所有儿子中，选择权值大于等于它且权值最小的儿子，走到那个儿子上。
• 如果不存在这样的儿子，它将停在当前节点。

问这个数字最终停在哪个节点。

$m$ 次操作，每次操作为修改一个点的权值，或者查询一个数字 $c$ 从根节点出发最终到达的点的编号。

输入格式

第一行两个数 $n, m$，为树的节点数和操作数。

接下来一行 $n$ 个整数，第 $i$ 个数表示 $i$ 号点的权值 $w_i$。

接下来 $n − 1$ 行，每行两个正整数 $x, y$ 描述树上的一条边 $(x, y)$。

接下来 $m$ 行每行描述一个操作，有如下两种格式：

• 1 a b：表示把 $a$ 节点的权值改成 $b$。
• 2 c：表示查询数字 $c$ 从根节点出发最终到达的点的编号。

注意 $1$ 号点的权值并无意义，你不需要关心它以及对它的修改（尽管这样的修改可能存在）。

数据保证任意时刻所有点的权值互不相同。

输出格式

对于每个查询操作，输出一行一个整数，表示数字 $c$ 最终到达的节点的编号。

样例

样例 1

5 5 
6 7 8 4 2
1 2
1 3
3 4
3 5
2 8
2 4
1 3 5
2 1
2 3

3
2
5
4

样例 2，3，4

见附加文件中的 fall/fall*.in 与 fall/fall*.ans。

测试点约束

对于所有数据，保证 $1\le n,m\le 2\times 10^5$，$1\le w_i,b,c\le 10^9$。