题目描述

小明在放学路上发现了一棵神奇的花树，假设 $1$ 为这棵树的根节点，并且在这棵树上一共有 $n$ 个节点，每个节点上都有一朵美丽的花，我们定义第 $n$ 朵 花的美丽值为 $a_i$ ，接下来将会经过 $m$ 天，每一天可能会发生下面两种事件中 的一种：

● 给出三个整数 $1$, $u$, $w$ 表示把第 $u$ 朵花的美丽值变为 $w$。

● 给出两个整数 $2$, $u$ 表示询问以 $u$ 为根节点的子树中美丽值最大的节点的值。

小明想在母亲节那天为妈妈摘下整棵树中最美丽的花朵作为礼物，因此他需 要每天精准掌握这颗花树的每个事件，请你帮助他设计一个程序来完成吧。

输入格式

第一行输入两个整数 $n$, $m$ 分别代表节点个数和将会经过的天数。
的一行有 $n$ 个整数,第 $i$ 个整数 $a_i$ 代表这朵花的美丽值。
$n − 1$ 行每行两个整数 $u$ 和 $v$ 表示节点 $u$ 和 $v$ 之间有一条边。
接下来的 $m$ 行将会保证以下格式：
一行中给出三个整数 $1$, $u$, $w$。
一行中给出两个整数 $2$, $u$。

输出格式

对于每一种事件 $2$，每行给出一个整数代表答案。

输入输出样例 #1

输入 #1

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

输出 #1

6
3
7
6

输入输出样例 #2

输入 #2

10 12
6 97 10 47 28 29 18 66 48 45
2 1
1 3
4 8
1 7
6 10
5 1
4 6
4 9
1 4
2 9
2 4
2 1
1 10 11
2 5
2 5
1 1 10
2 3
1 4 11
2 4
2 3
1 9 3

输出 #2

48
66
97
28
28
10
66
10