给定一个索引为 1、权重为 0 的树节点。令 cnt 为任意时刻树中的节点数(最初,cnt 设置为 1)。支持以下两种类型的Q查询:
- $$\mathrm{RW}$$ 添加一个权重为 W 的新节点(索引 cnt + 1),并在节点 R 和该节点之间添加边。
- $$2 R X = \pi$$ 输出以 R 开头的节点序列的最大长度。序列中的每个节点都是其前任节点的祖先。 序列中节点的权重之和不超过X。对于序列中连续的某些节点i, j,如果i是j的祖先,则w[i] ≥ w[j],并且从i到j的简单路径上不应该存在使得w[k] ≥ w[j]的节点k
树在任何时刻都以节点 1 为根。
请注意,查询是以修改后的方式给出的。
输入
第一行包含查询数量 Q (1 ≤ Q ≤ 400000)。
令last 为类型2 的前一个查询的答案(最初last 等于0)。
接下来的 Q 行中的每一行都包含以下形式的查询:
- 1 p q (1 ≤ p, q ≤ 1018):这是第一种类型的查询,其中 $$R = p \oplus last$$ 和 $${ \vec { w } } = q \oplus l a s t$$。保证1 ≤ R ≤ cnt和0 ≤ W ≤ 109。
- 2 p q (1 ≤ p, q ≤ 1018):这是第二种类型的查询,其中 $$R = p \oplus last$$ 和 $$X = q \oplus last$$。保证1 ≤ R ≤ cnt和0 ≤ X ≤ 1015。
$$a \oplus b$$ 表示 a 和 b 的按位异或。
保证至少存在一个类型 2 的查询。
输出
在单独的行中输出第二类型的每个查询的答案。
示例
输入 #1
6 1 1 1 2 2 0 2 2 1 1 3 0 2 2 0 2 2 2
输出 #1
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 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
输出 #3
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
输出#4
1 2 3
注意
在第一个示例中,
最后= 0
- 查询 1:1 1 1,权重为 1 的节点 2 添加到节点 1。
- 查询 2:2 2 0,从 2 开始的节点序列的权重不小于或等于 0。last = 0
- 查询 3:2 2 1,答案为 1,因为序列将为 {2}。最后= 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}。最后 = 2