You may have seen some similar problems before, but please, notice the difference in path values.

You are given a tree with nodes labelled from to , the root of which is the node labelled . Every node in the tree will be endowed with values related to given parameters , and each edge in the tree is endowed with a given bitwise operator which is one of the bitwise OR '|', the bitwise AND '&' and the bitwise XOR '^'

For any pair of nodes indicating the -th and the -th node in the tree, the shortest path connecting them in the tree, denoted by


together with operators along the path provide a value associated with given by


where is the operator on the edge between the node and the node in this path.

Now you are given queries, each of which contains two integers and . For this query, the value of the -th node will be set to be , and you are asked to calculate the bitwise OR, AND and XOR sum respectively of values for all the pairs where the -th node is an ancestor of the -th node. Note that a node is not considered as an ancestor of itself.

The first line contains two integers  and  indicating the size of the tree and the number of queries.

The second line contains  integers  descirbed as above.

The following  lines describe the tree. The -th line of them contains two integers  and  which describe that the -th node is the parent node of the -th node, and the edge connecting the -th node and the -th node is endowed with a bitwise operator: if  the operator is '|'; if  the operator is '&'; and if  the operator is '^'.

Each of the following  lines contains two integers  and  describing a query. It is guaranteed that the node  is not a leaf in the tree.

Output  lines corresponding to  given queries, the -th of which contains three integers representing the bitwise OR sum, the bitwise AND sum and the bitwise XOR sum for the -th query respectively.

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

7 1 4
6 0 6
12 0 12
14 6 8

In the sample case, the tree looks like

For the first query, the bitwise OR sum is .
For the second query, the bitwise OR sum is .