Mexor tree

A tree with $N$ vertices is given. Vertex $i$ has value $a_i$.

There are $M$ queries in total.

• $x$ $y$ $z$: Replace each value on the simple path between vertices $x$ and $y$ with the result of XOR-ing it with $z$.

After performing all $M$ queries, define a new sequence $b_i$ as follows.

• $b_i$ is the smallest non-negative integer that does not appear among the values on the simple path between vertex $S$ and vertex $i$. $(1 \leq i \leq N)$

Find all $b_i$.

The first line contains integers $N$ and $S$ separated by a space. $(1 \leq N \leq 300\,000, 1 \leq S \leq N)$

The second line contains the sequence $a_1, a_2, \cdots, a_N$ separated by spaces. $(0 \leq a_i \leq N)$

From the third line, the next $N-1$ lines each contain two integers $u, v$ separated by a space, meaning there is an edge between vertex $u$ and vertex $v$. $(1 \leq u,v \leq N)$

Line $N+2$ contains the number of queries $M$. $(1 \leq M \leq 300\,000)$

From line $N+3$, the next $M$ lines each contain three integers $x, y, z$ separated by spaces. $(1 \leq x,y,z \leq N)$

Print the sequence $b_1, b_2, \cdots, b_N$ separated by spaces on the first line.