You are given a tree with $N$ nodes, with each node assigned a value $v_i$. Support the following update:

• a b x XOR every other node on the path from $a$ to $b$ by $x$. (update node $a$, 3rd node on path $a$ to $b$, 5th node on path $a$ to $b$).

After all the updates, output the value of each node.

Input Specification

The first line of input contains $N$, and the number of updates $Q$.

The next line contains $N$ space-separated integers, $v_1,v_2,\dots ,v_N$.

The next $N-1$ lines contain two space-separated integers, $x_i{y}_i$, describing an edge connecting nodes $x_i$ and $y_i$.

The next $Q$ lines contain three space-separated integers, $a_i{b}_i{c}_i$, describing an update.

Output Specification

Output one line containing $N$ space-separated integers, the final value of node $1,2,\dots ,N$.

Constraints

$1\le a_i,b_i,x_i,y_i\le N$

$1\le c_i,v_i\le {10}^6$

Subtask 1 [20%]

$1\le N,Q\le 1000$

Subtask 2 [80%]

$1\le N\le 200000$

$1\le Q\le 100000$

Sample Input

7 2
0 0 0 0 0 0 0
1 2
2 3
3 4
1 5
5 6
6 7
4 7 2
3 6 3

Sample Output

3 2 3 2 2 3 2