圣剑护符

题目背景

小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` 。

输入输出样例

输入样例 #1

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

输出样例 #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}$