Cow Land Route Enjoyment

Cow Land has \(N\) distinct attractions (\(2 \le N \le 10^5\)) connected by \(N-1\) roads forming a tree (i.e. there is exactly one simple path between any two attractions).

Each attraction \(i\) has an enjoyment value \(e_i\) which may change over time. When cows travel from attraction \(i\) to attraction \(j\), they experience the attractions along the unique path between \(i\) and \(j\). The enjoyment value of the route is defined as the bitwise XOR of the enjoyment values of all attractions on that path.

You are to process \(Q\) operations. There are two types of operations:

• Q u v: Query the enjoyment value on the path from attraction u to attraction v.
• U u w: Update the enjoyment value of attraction u to w.

Help the cows determine the enjoyment value for each planned trip.

inputFormat

The first line contains two integers \(N\) (the number of attractions) and \(Q\) (the number of operations).

The second line contains \(N\) integers: \(e_1, e_2, \dots, e_N\) representing the initial enjoyment values of the attractions.

The following \(N-1\) lines each contain two integers \(u\) and \(v\) denoting a road connecting attractions \(u\) and \(v\).

The next \(Q\) lines each describe an operation in one of the following formats:

• Q u v - Query the XOR of enjoyment values from attraction \(u\) to attraction \(v\).
• U u w - Update the enjoyment value of attraction \(u\) to \(w\).

outputFormat

For each query operation (lines starting with Q), output the corresponding enjoyment value (the XOR of all attraction values along the path) on a new line.

sample

3 3
1 2 3
1 2
2 3
Q 1 3
U 2 4
Q 1 3

0
6