Tree
Description
You are given a node of the tree with index 1 and with weight 0. Let cnt be the number of nodes in the tree at any instant (initially, cnt is set to 1). Support Q queries of following two types:
-
Add a new node (index cnt + 1) with weight W and add edge between node R and this node. -
Output the maximum length of sequence of nodes which - starts with R.
- Every node in the sequence is an ancestor of its predecessor.
- Sum of weight of nodes in sequence does not exceed X.
- For some nodes i, j that are consecutive in the sequence if i is an ancestor of j then w[i] ≥ w[j] and there should not exist a node k on simple path from i to j such that w[k] ≥ w[j]
The tree is rooted at node 1 at any instant.
Note that the queries are given in a modified way.
First line containing the number of queries Q (1 ≤ Q ≤ 400000).
Let last be the answer for previous query of type 2 (initially last equals 0).
Each of the next Q lines contains a query of following form:
- 1 p q (1 ≤ p, q ≤ 1018): This is query of first type where
and 
. It is guaranteed that 1 ≤ R ≤ cnt and 0 ≤ W ≤ 109. - 2 p q (1 ≤ p, q ≤ 1018): This is query of second type where
and 
. It is guaranteed that 1 ≤ R ≤ cnt and 0 ≤ X ≤ 1015.
denotes bitwise XOR of a and b.
It is guaranteed that at least one query of type 2 exists.
Output the answer to each query of second type in separate line.
Input
First line containing the number of queries Q (1 ≤ Q ≤ 400000).
Let last be the answer for previous query of type 2 (initially last equals 0).
Each of the next Q lines contains a query of following form:
- 1 p q (1 ≤ p, q ≤ 1018): This is query of first type where and . It is guaranteed that 1 ≤ R ≤ cnt and 0 ≤ W ≤ 109.
- 2 p q (1 ≤ p, q ≤ 1018): This is query of second type where and . It is guaranteed that 1 ≤ R ≤ cnt and 0 ≤ X ≤ 1015.
denotes bitwise XOR of a and b.
It is guaranteed that at least one query of type 2 exists.
Output
Output the answer to each query of second type in separate line.
Samples
6
1 1 1
2 2 0
2 2 1
1 3 0
2 2 0
2 2 2
0
1
1
2
6
1 1 0
2 2 0
2 0 3
1 0 2
2 1 3
2 1 6
2
2
3
2
7
1 1 2
1 2 3
2 3 3
1 0 0
1 5 1
2 5 0
2 4 0
1
1
2
7
1 1 3
1 2 3
2 3 4
1 2 0
1 5 3
2 5 5
2 7 22
1
2
3
Note
In the first example,
last = 0
- Query 1: 1 1 1, Node 2 with weight 1 is added to node 1.
- Query 2: 2 2 0, No sequence of nodes starting at 2 has weight less than or equal to 0. last = 0
- Query 3: 2 2 1, Answer is 1 as sequence will be {2}. last = 1
- Query 4: 1 2 1, Node 3 with weight 1 is added to node 2.
- Query 5: 2 3 1, Answer is 1 as sequence will be {3}. Node 2 cannot be added as sum of weights cannot be greater than 1. last = 1
- Query 6: 2 3 3, Answer is 2 as sequence will be {3, 2}. last = 2