树和序列
题号：NC236244
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

你有一棵树，初始只有一个权为0的节点1，假设 cnt 是目前这棵树的节点总数，你需要维护以下两个操作：

  • ，添加一个新的节点  ，它的父节点是 R ，权为 W 。

  • ，你需要构造一个尽可能长的序列 S ，满足如下条件：

    1. 序列第一个元素是 R 。

    2. 对于序列中的任意一个元素 S_i , S_i 是  在树上的祖先。

    3. 序列中的所有元素对应的节点的权值之和不应超过 X 。

    4. 对于序列中的任意一个元素 S_i ，  ，并且从  到 S_i 的简单路径上，不能存在一个 k 满足  。

对于操作2，输出 S 的最大长度。

本题强制在线。

输入描述:

第一行输入一个整数  ，表示操作个数。
让 last 表示上一个操作2的查询答案（初始为0）。
接下来 Q 行，每行按照以下格式输入：
，对应  ，  ，并且保证  。
，对应  ，  ，并且保证  。
其中  表示 a 和 b 二进制异或的值。
输入保证至少有一个操作2。

输出描述:

对于每一个查询，输出一行一个整数，表示 S 的最大长度。
示例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