James' XOR Update

View as PDF

Points: 12 (partial)
Time limit: 1.0s
Memory limit: 128M

Author:
Problem type

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

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

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

Input Specification

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

The next line contains space-separated integers, .

The next lines contain two space-separated integers, , describing an edge connecting nodes and .

The next lines contain three space-separated integers, , describing an update.

Output Specification

Output one line containing space-separated integers, the final value of node .

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