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: - ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF932D/da4b1378453cb99e049b53a08b0ba18e7ba1e551.png) Add a new node (index $ cnt+1 $ ) with weight $ W $ and add edge between node $ R $ and this node. - ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF932D/ed73083bdc6b75130b20ebceb85afda31415dcb3.png) 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<=10^{18} $ ): This is query of first type where ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF932D/330f4f80e58dcf1ca75ad091d4b205adf1d76c24.png) and ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF932D/5feb6a3312a35a5a19bda784c33f92aaadc2ed58.png). It is guaranteed that $ 1<=R<=cnt $ and $ 0<=W<=10^{9} $ . - 2 p q ( $ 1<=p,q<=10^{18} $ ): This is query of second type where ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF932D/330f4f80e58dcf1ca75ad091d4b205adf1d76c24.png) and ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF932D/9c16bf145a73cc846106881a02e5f7cceb5ee2f7.png). It is guaranteed that $ 1<=R<=cnt $ and $ 0<=X<=10^{15} $ . ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF932D/79cc482b9c190fd9e8196fcbaf085328720025f7.png) 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

输出样例 #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

说明

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 $