Klasika

Time limit5sMemory limit512 MB

Summary

Nodes are added as leaves to a rooted tree with XOR edge weights, and each query asks for the maximum XOR path from node a to any node in the subtree of b.

Level: Medium7 of 10
Topics: Trie, Bit manipulation, Tree
Solved: No attempts yet

Problem

The tree starts with one node, node 1, which is the root. Process $Q$ queries on this tree.

Add x y: Adds a new node as a child of node x. The new node and x are connected by an edge with weight y. The new node is numbered by the node count of the tree after the addition.
Query a b: Finds the longest path that starts at node a and ends at some node in the subtree of b, with b itself included. The length of a path is the XOR of all edge weights on it.

Input

The first line contains $Q$ ( $1 \le Q \le 200000$ ). Each of the next $Q$ lines holds one query. The values x, a, and b always refer to existing nodes at that moment, and y is at most $2^{30}$ .

Output

For each Query, print the answer on its own line, in the order the queries appear in the input.

Examples3

Example 1

Input

4
Add 1 5
Query 1 1
Add 1 7
Query 1 1

Expected output

5
7

Example 2

Input

6
Add 1 5
Add 2 7
Add 1 4
Add 4 3
Query 1 1
Query 2 4

Expected output

7
2

Example 3

Input

10
Add 1 4
Add 1 9
Add 1 10
Add 2 2
Add 3 3
Add 4 4
Query 4 2
Query 1 3
Add 6 7
Query 1 3

Expected output

14
10
13