3389. Chrismas Tree

Description

Here is a tree withvertices. Let me remind you that a tree ofvertices is an undirected connected graph ofvertices andedges that does not contain cycles.

Let's denote the distance of two vertices are the amounts of edges of one shortest path between these two vertices.

There are  gifts on vertex() initially, and we have four kinds of options which are numbered from 1 to 4:

  1. Add one gift to every vertex which satisfied that the distance between and is exactly one.

  2. Add one gift to vertex .

  3. Remove gifts from vertex u, and after this operation is always non-negative.

  4. Ask you the bitwise XOR of the amount of gifts on every vertex which satisfied that the distance between and is exactly one. In another word, let's denote and your task is to calculateafter is given.

There are totally operations and we want to know the answer after every operation of the 4th format.

Input

The first line contains two integers.

The next  lines contain two integersrepresent an edge of the tree.

The next line containsintegers, represent the amount of gifts on vertexinitially.

For the next  lines , each line is in one of the following four formats:

  • , and we make sure that is always non-negative after this operation.

and the implications of these four operations are mentioned above.

Output

For each operation of the 4th format, output the answer in one line.

Sample Input

3 4
1 2
2 3
4 2 1
1 1
2 2 
3 1 1
4 2

Sample Output

2

Note

 


难度等级: 0
总通过次数: 3
总提交次数: 30