Path Subset XOR Equivalence

You are given a tree of n nodes, numbered from \(1\) to \(n\). Each node is assigned an integer value \(v_i\) whose binary representation indicates the possession of certain properties. Two nodes are connected by \(n-1\) edges forming a tree structure.

For any subset of nodes, the combined property value is defined as the bitwise XOR of the values of the nodes in the subset. (Note that the property value of the empty set is defined to be \(0\).)

There are two types of operations:

1. Query Operation: Given two nodes \(x\) and \(y\), consider the simple path between them (i.e. the set of nodes along the unique simple path in the tree). Determine whether there exist two different (not necessarily disjoint) subsets of the nodes on this path such that their combined property (XOR) values are equal.

   Hint: Note that the empty set is considered a valid subset. It can be shown that two distinct subsets yield the same XOR value if and only if there exists a nonempty subset of these nodes whose XOR is \(0\). Equivalently, if we denote \(|S|\) as the number of nodes on the path and \(\text{rank}(S)\) as the rank (over \(\mathbf{F}_2\)) of the set of numbers, the answer is "Yes" if and only if \(|S| > \text{rank}(S)\).

2. Update Operation: Given two nodes \(x\) and \(y\) and an integer \(k\), update each node on the simple path between \(x\) and \(y\) by flipping some of its bits – that is, perform \(v = v \oplus k\) for each node on the path.

Input/Output Example:

Consider a test case where the tree has 5 nodes and 5 operations. The input might be:

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

The operations are as follows:

• Query from node 3 to node 4 (path: 3,2,4) yields output No (since no non‐empty subset has XOR 0).
• Update the path between node 1 and node 2 with k = 1 (updating nodes 1 and 2).
• Query from node 1 to node 3 (path: 1,2,3) yields output Yes (since after the update, the values become \(0,3,3\) and a nonempty subset \(\{3,3\}\) has XOR 0).
• Update the path between node 2 and node 5 with k = 2.
• Query from node 5 to node 4 (path: 5,1,2,4) yields output Yes (since the nodes become \(7,2,1,4\) and \(2 \oplus 1 \oplus 4 = 7\)).

Your task is to process the operations in order. For each query (type 1) output either Yes or No as described.

Note: You may assume that the number \(n\) and the number of operations \(q\) are small enough so that a solution which processes each path by explicitly enumerating the nodes along it will run in time.

inputFormat

The first line contains two integers \(n\) and \(q\) which denote the number of nodes and the number of operations respectively.

The second line contains \(n\) integers \(v_1, v_2, \ldots, v_n\) where \(v_i\) is the initial value of the \(i\)th node.

The next \(n-1\) lines each contain two integers \(u\) and \(v\) indicating that there is an edge connecting node \(u\) and node \(v\).

The following \(q\) lines describe the operations. Each operation is in one of the following two formats:

• 1 x y — Query: check if the simple path from \(x\) to \(y\) contains two different subsets with equal XOR value.
• 2 x y k — Update: for all nodes on the simple path from \(x\) to \(y\), update the value by doing \(v = v \oplus k\) (where \(\oplus\) denotes bitwise XOR).

outputFormat

For each query operation (type 1), output a single line containing either Yes if there exist two distinct subsets of the nodes on the specified path with the same combined XOR value, or No otherwise.

sample

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

No
Yes
Yes

</p>