题目背景

CaiZi 讨厌三角形，但是他喜欢树。

2024.8.15 Update：增加了一组 hack 数据。

题目描述

给定一颗有 $n$ 个点的树，节点编号为 $1\sim n$，每个点有点权，开始时点 $i$ 的点权为 $a_i$。共有 $q$ 次操作。

1. 将点 $x$ 到点 $y$ 的简单路径上的点的点权异或 $k$。
2. 判断能否在点 $x$ 到点 $y$ 的简单路径上选 $3$ 个不同点，并以这 $3$ 个点的点权为边长构成三角形。特别的，如果无法选出 $3$ 个点，也视为不能构成三角形。

点 $x$ 到点 $y$ 的简单路径：点 $x$ 到点 $y$ 不重复走过任何一条边的路径。其上的所有点为这条路径上所有的点，包括点 $x$ 和点 $y$。

保证任何时刻不会有任何一个点的点权为 $0$。

输入格式

第一行输入 $2$ 个整数 $n,q$，分别表示这棵树点的个数、操作的个数。

第二行输入 $n$ 个整数 $a_i$，表示开始时点 $i$ 的点权。

接下来 $n-1$ 行，每行输入 $2$ 个整数 $u,v$，表示这棵树的一条边。

接下来 $q$ 行，每行先输入 $1$ 个整数 $s$，表示操作类型。

• 若 $s=1$，则再输入 $3$ 个整数 $u,v,w$，表示一次修改操作。
• 若 $s=2$，则再输入 $2$ 个整数 $u,v$，表示一次询问操作。

输出格式

对于每次询问操作，若能满足条件输出 $1$，否则输出 $0$，无需空格或换行。

5 5
1 2 3 4 5
1 2
1 3
2 4
2 5
2 1 2
2 3 4
1 3 5 4
2 2 3
2 1 5

0110

提示

【样例解释】

第 $1$ 次操作时简单路径上的点权少于 $3$ 个。
第 $2$ 次操作时简单路径上的点权分别为 $1,2,3,4$。
第 $3$ 次操作后点 $1\sim n$ 的点权分别为 $5,6,7,4,1$。
第 $4$ 次操作时简单路径上的点权分别为 $5,6,7$。
第 $5$ 次操作时简单路径上的点权分别为 $1,5,6$。

【数据范围】

本题采用捆绑测试。

• Subtask #1（$8\text{ pts}$）：$n,q\le3\times10^3$。
• Subtask #2（$8\text{ pts}$）：保证这棵树是一朵菊花。
• Subtask #3（$20\text{ pts}$）：每次修改操作时 $x=y$。
• Subtask #4（$24\text{ pts}$）：保证这棵树是一条链。
• Subtask #5（$40\text{ pts}$）：无特殊性质。依赖 Subtask #1 到 Subtask #4。

对于 $100\%$ 的数据，$1\le u,v\le n\le10^5$，$1\le q\le10^5$，$s\in\{1,2\}$，$1\le a_i,w\le 2^{31}-1$。