CF932D.Tree

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.

给你一棵树，初始时仅包含编号为 1 的节点，其权值为 0。令 cnt 表示任意时刻树中节点的总数（初始时 cnt 设为 1）。你需要支持 Q 个如下两种类型的查询：

• 添加一个新节点（编号为 cnt + 1），其权值为 W，并在节点 R 与该新节点之间添加一条边。
• 输出满足以下条件的节点序列的最大长度：
  1. 序列以节点 R 开始；
  2. 序列中每个节点均为其前驱节点的祖先；
  3. 序列中所有节点的权值之和不超过 X；
  4. 对于序列中任意两个相邻节点 i, j，若 i 是 j 的祖先，则必须满足 w[i] ≥ w[j]，且在 i 到 j 的简单路径上不存在节点 k 满足 w[k] ≥ w[j]。

在任意时刻，树均以节点 1 为根。

注意：查询是以一种变形方式给出的。

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.

第一行包含查询次数 $ Q $（$ 1 \leq Q \leq 400000 $）。

令 $ last $ 表示上一个类型为 2 的查询的答案（初始时 $ last = 0 $）。

接下来的 $ Q $ 行中，每行包含如下形式之一的查询：

• 1 p q（$ 1 \leq p, q \leq 10^{18} $）：这是第一类查询，其中
  
  且
  。
  保证 $ 1 \leq R \leq cnt $ 且 $ 0 \leq W \leq 10^9 $。

• 2 p q（$ 1 \leq p, q \leq 10^{18} $）：这是第二类查询，其中
  
  且
  。
  保证 $ 1 \leq R \leq cnt $ 且 $ 0 \leq X \leq 10^{15} $。

表示 $ a $ 与 $ b $ 的按位异或（XOR）运算。

保证至少存在一个类型为 2 的查询。

Output the answer to each query of second type in separate line.

对每个第二类查询，将答案输出在单独的一行中。

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

在第一个样例中，

_last_ = 0

• 查询 1：1 1 1，将权值为 1 的节点 2 加入节点 1。
• 查询 2：2 2 0，不存在从节点 2 出发、权值和不超过 0 的节点序列。_last_ = 0
• 查询 3：2 2 1，答案为 1，因为序列为 {2}。_last_ = 1
• 查询 4：1 2 1，将权值为 1 的节点 3 加入节点 2。
• 查询 5：2 3 1，答案为 1，因为序列为 {3}；节点 2 不能加入，因为权值和不能超过 1。_last_ = 1
• 查询 6：2 3 3，答案为 2，因为序列为 {3, 2}。_last_ = 2