题目描述

Haruna每天都会给提督做早餐！这天她发现早饭的食材被调皮的Shimakaze放到了一棵树上，每个结点都有一样食材。Shimakaze要考验一下她。

每个食材都有一个美味度，Shimakaze会进行两种操作：

1. 修改某个结点的食材的美味度。
2. 对于某条链，询问这条链的美味度集合中，最小的未出现的自然数是多少。即mex值。

请你帮帮Haruna吧。

输入格式

第一行包括两个整数 $n$，$m$，代表树上的结点数(标号为1~n)和操作数。

第二行包括 $n$ 个整数 $a_1,\ldots,a_n$，代表每个结点的食材初始的美味度。

接下来 $n-1$ 行，每行包括两个整数 $u$，$v$，代表树上的一条边。

接下来 $m$ 行，每行包括三个整数：

• $0\ u\ x$ 代表将结点 $u$ 的食材的美味度修改为 $x$。
• $1\ u\ v$ 代表询问以 $u$，$v$ 为端点的链的mex值。

输出格式

对于每次询问，输出该链的mex值。

输入样例

10 10
1 0 1 0 2 4 4 0 1 0
1 2
2 3
2 4
2 5
1 6
6 7
2 8
3 9
9 10
0 7 14
1 6 6
0 4 9
1 2 2
1 1 8
1 8 3
0 10 9
1 3 5
0 10 0
0 7 7

输出样例

0
1
2
2
3

提示

• $1\le n\le5\times10^4$
• $1\le m\le5\times10^4$
• $0\le a_i\le10^9$