Klasika

시간 제한5초메모리 제한512 MB

요약

루트가 있는 트리에 가중치 간선을 가진 노드를 추가하고, 각 질의에서 노드 a에서 b의 서브트리 안 임의의 노드까지 XOR 값이 최대인 경로를 구합니다.

문제

처음에는 루트인 1번 노드 하나로 이루어진 트리가 있다. 이 트리에 대해 $Q$ 개의 질의를 처리하시오.

Add x y: 노드 x의 자식으로 새 노드를 추가한다. 새 노드와 x는 가중치 y인 간선으로 연결된다. 새 노드의 번호는 추가한 뒤 트리의 노드 개수와 같다.
Query a b: 노드 a에서 시작해 b의 서브트리에 속한 어떤 노드에서 끝나는 경로 중 가장 긴 경로를 찾는다. b 자신도 서브트리에 포함된다. 경로의 길이는 경로에 포함된 모든 간선 가중치의 XOR이다.

첫 줄에 질의 개수 $Q$ 가 주어진다 ( $1 \le Q \le 200000$ ). 이후 $Q$ 개의 줄에 질의가 한 줄에 하나씩 주어진다. x, a, b는 그 시점에 존재하는 노드를 가리키며, y는 $2^{30}$ 이하이다.

각 Query 질의에 대한 답을 입력 순서대로 한 줄에 하나씩 출력한다.

예제 1

입력

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

예상 출력

5
7

예제 2

입력

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

예상 출력

7
2

예제 3

입력

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

예상 출력

14
10
13