Pog plays a game with szh and this time he finds another tree, this tree is different from the previous one, all nodes of which have a weight! And the weight of the $i-th$ node is $a_i$.
Pog and Szh choose two different nodes on the tree, then pog walks to szh along the paths of the tree and records the weight. Because of too many nodes, pog only records the XOR of all weight of the nodes he passes for convenient.Due to szh's love for pog,szh wanders the sum of which pog records for any $n*(n-1)$ different combinations.
Because of tired of szh's corny pursuit, pog changes $a_A$ into $B$ at every moment, of course, szh must output the answer of all moment.
Input
Several groups of data (no more than $3$ groups,$n \geq 1000$).
In every group, two integers at first line are $n(2 \leq n \leq 10000)$ and $Q(1 \leq Q \leq 10000)$.
At the following line, $n$ integers are $a_i(0 \leq a_i < 32768)$.
At the following $n-1$ line, two integers are $b_i$ and $c_i$ at every line, it shows an edge connecting $b_i$ and $c_i$.
At the following $Q$ line, two integers are $A(1 \leq A \leq n)$ and $B(0 \leq B < 32768)$ at every line, it shows that changing $a_A$ into $B$.
Output
For each inquire to each group of data, output a line , which shows all the sum of which pog records in different combinations.
