Description

The sacred sword in front of Xiao L and Xiao K is made of $n$ talismans, numbered $1,2,\ldots,n$. There are $n-1$ spell-power lines connecting pairs of talismans, forming a tree structure.

After a long period of research, they found that the interaction between talismans is not complicated. Each talisman has an attribute value; the attribute value of talisman $i$ is denoted by $v_i$. Each bit ($0$ or $1$) in the binary representation of this value indicates whether the talisman has a certain attribute. The same bit position across all attribute values corresponds to the same attribute.

For a collection of talismans (a set of talismans), for each specific attribute, count how many talismans in the collection contain this attribute. If the count is even, then this collection produces interference, and the corresponding bit in the final attribute value is $0$. If the count is odd, then after interference there remains the influence of one talisman, and the corresponding bit is $1$. In other words, the attribute value of a set of talismans is the XOR sum of the attribute values of the individual talismans. The attribute value of the empty set is defined as $0$.

Now, Xiao L wants to know: if we take all talismans on the simple path between two talismans $x$ and $y$, can we find two different subsets such that the two subsets have the same attribute value (note that the empty set is also a subset of the set of all talismans on the path). Meanwhile, Xiao K will also take out all talismans on the path between the two talismans and adjust them, modifying the attribute values of all these talismans on some same bit positions (i.e., changing $0$ to $1$ and $1$ to $0$). This can be seen as XOR-ing the attribute values of all these talismans with a value.

Input Format

The first line contains two integers $n,q$, representing the number of talismans and the number of operations by Xiao L and Xiao K.

The next line contains $n$ integers. The $i$-th number is the attribute value $v_i$ of talisman $i$.

The following $n-1$ lines each contain two integers $x,y$, indicating that there is a spell-power line connecting talismans $x$ and $y$. It is guaranteed to form a tree structure.

The next $q$ lines each describe an operation in one of the following forms:

1. Update x y z: XOR the attribute values of all talismans on the simple path between talismans $x$ and $y$ with a value $z$.

2. Query x y: Determine whether, for the set of talismans on the simple path between talismans $x$ and $y$, there exist two different subsets such that their attribute values are the same.

Output Format

For each Query operation, output one line containing YES or NO.

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

NO
YES

Hint

For some reason, this problem uses bundled testdata. You can get the full score of a subtask only if you pass all test points in that subtask; otherwise you get $0$ points.

$Subtask\#1$: $20pts$, the distance between $x$ and $y$ in the tree is at most $5$.

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

$Subtask\#3$: $40pts$, no special constraints.

For $100\%$ of the data, $1\le n,q\le 10^5$, $1\le x,y\le n$, $0\le v_i,z<2^{30}$.

Translated by ChatGPT 5