“To strengthen the fundamental skills in data structures and gain a profound understanding of the essence of data structures, as well as to implement code effectively, we need to make efforts to study the profound connotation of data structures...”

The ACM Training Base is having a meeting, but after listening to only two sentences, Capoo the cat falls asleep. When he wakes up, he feels at a loss facing the homework left behind. Luckily, he knows a data structure expert, which is you! In order to prevent poor Capoo from being scolded by his senior, you decide to help him complete his data structure homework.

[capoo_confused.jpg](Please imagine it, we can't display it for you due to copyright reasons. T.T)

The homework questions are as follows:

Given a tree rooted at node , each node in the tree has a node weight . Now, you need to perform operations, which can be divided into two types:

•   , which means setting the node weights of all the nodes on the simple path between and (inclusive) to .
•   , which means querying the number of pairs of nodes in the subtree rooted at such that and holds.

Here, represents the bitwise XOR operation, similar to the XOR operator (^) in C/C++.

refers to the lowest common ancestor of nodes and . For example, in Sample 3, .

输入描述:

The first line consists of two integers,  and  , representing the number of nodes in the tree and the number of operations, respectively.

The second line contains  integers,  , representing the initial node weights.

The third line contains  integers, where the th integer,  , represents the existence of an edge between the th node and the th node.

Following are  lines, each representing an operation:

For each operation, the first integer of the line,  , denotes the type of operation.
If , then the next three integers, , , and  , represent the two endpoints of the covered chain and the assigned weight for that chain.
If , then the next integer,  , represents the root node of the subtree for which a query is required.

输出描述:

For each query, output a single line containing an integer representing the answer to that query.

2 1
0 0
1
2 1

1

3 3
0 0 1
1 1
2 1
1 1 2 1
2 1

1
0

5 5
1 0 0 1 1
1 1 3 3
1 5 4 1
1 2 4 0
2 3
1 2 1 1
2 1

1
5

For Sample 3, in the first query, after the first two coverings, the node weights of the tree become , and the valid point pairs in subtree 3 are .

In the second query, after the first three coverings, the node weights of the tree become , and the valid point pairs in subtree 1 are .