题目描述

小明在放学路上发现了一棵神奇的花树，假设 $1$ 为这棵树的根节点，并且在这棵树上一共有 $n$ 个节点，每个节点上都有一朵美丽的花，我们定义第 $i$ 朵花的美丽值为 $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

说明/提示

样例解释

对于样例 1，第一天以 2 为根节点的子树中美丽值最大的节点是 6，它的美丽值是 6。

第二天以 3 为根节点的子树只有它自己一个节点，所以最大美丽值节点就是它自己，值为 3。

接下来第三天将节点 3 的值变为 7。

第四天以 1 为根节点的子树就是这棵树本身，同时美丽值最大的节点为 3，它的美丽值为 7。

最后第五天以 2 为根节点的子树中美丽值最大的节点是 6，它的美丽值是 6。

数据范围

• 对于 30% 的数据，保证 $1 \le n,m \le 5 \times 10^3$。
• 对于另外存在 20% 的数据保证只有事件 $2$。
• 对于 100% 的数据，保证 $1 \le n,m \le 2 \times 10^5, \;1 \le a_i, w \le 1 \times 10^9$。