题目背景

小L和小K正在研究传说中的圣剑。

“所谓圣剑，是封入了各种护符并将其固定为刀剑外形的一种东西。据说一旦用咒力线把护符们接合在一起，就会产生复杂的相互干涉作用。”

题目描述

小L和小K面前的圣剑由 $n$ 块护符组成，分别编号为 $1,2,\ldots , n$ ，有 $n-1$ 条咒力线连接两块护符，形成了一个树形结构。

经过小L和小K的长时间的研究，他们发现护符之间的相互作用并不复杂。每块护符都有一个属性值，第 $i$ 块护符的属性值记为 $v_i$ 。这个值的每个二进制位上的 $0$ 或 $1$ 表示这块护符是否拥有特定属性。所有属性值中相同的二进制位对应的是相同的属性。

对于一系列护符（护符的集合），对于每种特定属性，统计其中包含这一属性的护符数量，如果为偶数，则这一系列护符形成了干涉，最终的属性值对应的二进制位上为 $0$ ，如果为奇数则干涉后剩下了一块护符的影响，对应的二进制位为 $1$ 。也就是说， 护符集合的属性值为单个护符的属性值的异或和 。 空集的属性值定义为 $0$ 。

现在，小L想知道，如果取出两块护符 $x,y$ 间的简单路径上的所有护符，能否找到两个不相等的子集，使得两个子集的属性值相同（注意到空集也是路径上所有护符集合的子集）。同时，小K还会将两块护符间的路径上的所有护符取出进行调整，将所有这些护符的属性值在某些相同二进制位上进行修改（即 $0$ 变为 $1$ ， $1$ 变为 $0$ ），可以看做是将所有这些护符的属性值异或上了一个值。

输入格式

输入的第一行为两个整数 $n,q$ ，分别表示护符的数量和小L和小K的操作的数量。

下一行有 $n$ 个整数，第 $i$ 个数表示第 $i$ 块护符的属性值 $v_i$ 。

接下来的 $n-1$ 行，每行有两个整数 $x,y$ ，表示有一条咒力线连接了 $x,y$ 两块护符。保证形成一个树形结构。

接下来的 $q$ 行，每行一个操作，形式如下：

1. Update x y z ：将编号分别为 $x,y$ 的两块护符间的简单路径上的所有护符的属性值异或上一个值 $z$ 。

2. Query x y ： 判断对于编号分别为 $x,y$ 的两块护符间的简单路径上的护符的集合，是否存在两个不相等的子集，使得两个子集的属性值相同。

输出格式

对于每个 Query 操作，输出一行 YES 或 NO 。

2 3
3 4
1 2
Query 1 2
Update 2 2 7
Query 2 1

NO
YES

提示

由于某种原因，本题将采用 捆绑测试 。只有通过一个子任务内的所有测试点，才能得到该子任务的全部分数，否则得 $0$ 分。

$Subtask\#1$ ： $20pts$ ， $x,y$ 在树上的距离小于等于 $5$ 。

$Subtask\#2$ ： $40pts$ ， $n,q\le 5000,0\le v_i,z\le 2^{10}$

$Subtask\#3$ ： $40pts$ ，无特殊限制。

对于 $100\%$ 的数据，有 $1\le n,q\le 10^5,1\le x,y\le n,0\le v_i,z< 2^{30}$