题目描述

给定一棵以 $1$ 为根的包含 $n$ 个节点的有根树。第 $i$ 个节点有点权 $a_i$。

定义函数 $f(u,v)$ 表示从 $u$ 到 $v$ 经过的所有节点的点权的可重集的中位数。

请注意，本题中的中位数的定义与数学中的定义略有不同：这里一个长度为 $t$ 的序列的中位数定义为这个序列第 $\left\lceil\frac{t+1}2\right\rceil$ 小的数。

定义函数 $\text{cover}(x_1,y_1,x_2,y_2)$ 表示从 $x_1$ 到 $y_1$ 的路径是否完全覆盖了从 $x_2$ 到 $y_2$ 的路径。如果完全覆盖，则 $\text{cover}(x_1,y_1,x_2,y_2)=1$，否则 $\text{cover}(x_1,y_1,x_2,y_2)=0$。

你需要依次处理 $q$ 次操作，按照以下格式给出：

1 u：表示一次操作，需要你将点 $u$ 的点权对 $1$ 异或；

2 u v：表示一次询问，需要你求出 $\max\limits_{1\le i\le n,1\le j\le n}\{\text{cover}(i,j,u,v)f(i,j)\}$。

对于第二类操作，保证每次询问均满足 $u$ 不是 $v$ 的祖先且 $v$ 不是 $u$ 的祖先，且 $u \neq v$。

你需要对于每个第二类操作，输出对应的值。

输入格式

第一行两个正数 $n$ 和 $q$，分别表示树的节点数与询问次数。

第二行 $n$ 个整数，第 $i$ 个数表示第 $i$ 个节点的点权 $a_i$。

下面 $n-1$ 行，每行两个整数 $x,y$，描述一条连接 $x$ 与 $y$ 的边。

下面 $q$ 行，每行先输入一个整数 $opt$，表示本次是是操作还是询问。若 $opt=1$，则这是一次操作，且接下来会输入一个整数 $u$；若 $opt=2$，则这是一次询问，且接下来会输入两个整数 $u,v$。其具体意义见【题目描述】。

输出格式

对于每次询问输出一行，即对应询问的答案。

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

3
4

提示

【样例解释】

第一次是询问。显然，只有 $(i=4,j=8)$ 满足 $\text{cover}(i,j,u,v)=1$。此时 $f(i,j)=3$。

第二次是操作。将 $3$ 号节点的点权改为了 $2$。

第三次是询问。当 $i=4,j=3$ 时，$\text{cover}(i,j,u,v)=1$ 且 $f(i,j)=4$。不难发现，对于其他所有满足 $\text{cover}(i,j,u,v)=1$ 的节点对 $(i,j)$，均没有 $f(i,j)>4$。

【数据范围】

• Subtask 1（8 pts）：$n,q\le50$；
• Subtask 2（12 pts）：$n,q\le2\times10^3$；
• Subtask 3（16 pts）：$n,q\le4\times10^4$；
• Subtask 4（10 pts）：保证树的形态随机生成；
• Subtask 5（12 pts）：保证没有 $1$ 操作；
• Subtask 6（12 pts）：保证每次询问的 $u,v$ 都是叶子节点；
• Subtask 7（30 pts）：无特殊限制。

Subtask 4 的随机方式为：随机生成一个的排列 $p$，对于 $i\in[2,n]$，$p_i$ 向 $p_1,p_2,...,p_{i-1}$ 中等概率随机的一个点连边。

对于 $100\%$ 的数据满足，$1\le n,q,a_i \le 10^5$，保证每次询问均满足 $u$ 不是 $v$ 的祖先且 $v$ 不是 $u$ 的祖先，且 $u \neq v$。