406835: GYM102566 L Unpredictable Tree

Bored of studying web design at university, Peter decided it's time to come back to his only friend: an unpredictable labeled rooted tree who always gives him mixed signals. Initially, the tree consists only of its root, a node with label 0. The signals either are information about changes of the shape of the tree, or questions about the current state of the tree (the tree has an existential crisis and does not know all the information about himself).

Thus, the tree gives Peter one of the following signals:

• $$$0$$$ $$$X$$$ $$$Y$$$ $$$V$$$ - a new node with label $$$X$$$ is created as node with label $$$Y$$$'s child, connected by an edge with cost $$$V$$$
• $$$1$$$ $$$X$$$ - the node with label $$$X$$$ is deleted, and all the children of this node are attached to node $$$X$$$'s father
• $$$2$$$ $$$X$$$ $$$Y$$$ - the node with label $$$X$$$ is moved as node with label $$$Y$$$'s child (keeping the same edge cost from node $$$X$$$ to the new father)
• $$$3$$$ $$$X$$$ $$$V$$$ - all the edges in node with label $$$X$$$'s subtree are XOR-ed with value $$$V$$$
• $$$4$$$ $$$X$$$ - find the XOR sum of the edges in node with label $$$X$$$'s subtree
• $$$5$$$ $$$X$$$ $$$Y$$$ - find the XOR sum of the edges on the path from $$$X$$$ to $$$Y$$$

The first line of the input will contain the number $$$S \leq 250.000$$$, representing the number of signals that Peter receives. Each of the following lines contains a signal, that Peter needs to process.

The labels of the nodes are integers between $$$0$$$ and $$$10^6$$$.

For signals of type $$$0$$$, $$$X$$$ has never been in a signal before and $$$0 \leq V \leq 2 * 10^9$$$.

For signals of type $$$1$$$, it is guaranteed that $$$X$$$ still exists in the tree.

For signals of type $$$2$$$, it is guaranteed that $$$Y$$$ is not in the subtree of node $$$X$$$.

For signals of type $$$3$$$, $$$0 \leq V \leq 2 * 10^9$$$.

The output file should contain the answer for each signal of type $$$4$$$ and $$$5$$$.

23
0 8 0 1
0 19 0 9
0 15 8 7
5 8 19
2 19 8
5 19 8
4 8
0 1 0 5
0 2 1 4
0 3 1 6
0 4 3 11
0 5 3 10
0 6 3 0
4 1
5 8 15
5 19 6
1 8
3 3 2
5 6 19
4 15
2 3 15
5 6 19
4 15

8
9
14
3
7
11
8
0
10
5