Tree
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

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
    1. starts with R.
    2. Every node in the sequence is an ancestor of its predecessor.
    3. Sum of weight of nodes in sequence does not exceed X.
    4. 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.

示例1

输入

复制 
6
1 1 1
2 2 0
2 2 1
1 3 0
2 2 0
2 2 2

输出

复制 
0
1
1
2
示例2

输入

复制 
6
1 1 0
2 2 0
2 0 3
1 0 2
2 1 3
2 1 6

输出

复制 
2
2
3
2
示例3

输入

复制 
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
示例4

输入

复制 
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

备注:

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