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 200\,000~

~1 \le Q \le 100\,000~

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