Description

Caca enjoys planting trees. He has planted a banana tree, but it seems only to grow with some artificial maintenance. So he will sometimes hang a blessing onto it. The so-called blessing is nothing but a chain. However, sometimes the tree is growing too well, leading the tree to become crooked. He has to do some pruning at times as well.

Caca loves mode, so he frequently inquires about the maximum occurrence of a certain value in the multiset formed by the depths of all existing nodes on the tree.

To be specific, there is a rooted tree. Initially, it contains the only node labeled $1$ as the root. There is a variable $n = 1$. There will be three types of operations as follows:

1. x l k: Attach $k$ chains, each of length $l$, under the node $x$. Formally, nodes labeled $(n + 1) \sim (n + lk)$ will be added, and for each $1 \leq i \leq k$, edge $(x, n + (i - 1)l + 1)$, as well as for each $2 \leq j \leq k$, edges $(n + (i - 1)l + j - 1, n + (i - 1)l + j)$, will be added. Afterwards, set $n \gets n + lk$.
2. x: Prune all the nodes in the subtree of $x$.
3. (No parameters): Inquiring about the maximum occurrence of a certain value in the multiset formed by the depths of all existing nodes on the tree.

Caca will perform $m$ operations in a row. For each operation of type $3$, please tell him the correct answer.

Input Format

The first line of input contains a single integer $m$.

Then $m$ lines follow. Each line contains an operation. The first integer you read, denoted as $\mathrm{op}$, indicates the type of the operation. Then some amount of parameters will be given in the same form above.

Output Format

For each operation of type $3$, print the correct answer in a new line.

23
3
1 1 2 3
3
1 6 2 2
3
1 7 1 4
3
2 12
3
2 13
3
1 3 1 2
3
2 7
3
2 3
3
1 5 2 3
3
2 6
3
2 5
3

1
3
5
6
5
5
6
4
3
5
3
2

16
1 1 4 3
3
1 2 3 3
3
1 10 1000000000 2
3
1 1000000021 1 10
3
2 1000000027
3
2 23
3
1 12 1 1
3
1 2000000033 100000 1000000000
3

3
6
8
12
11
7
8
1000000001

18
1 1 85 483
1 32607 44 379
2 45784
1 46178 133 40
3
1 13506 152 357
2 62124
3
1 70877 209 33
3
1 37299 429 158
3
1 31487 258 363
2 159051
3
2 227162
2 279608
3

902
1257
1257
1415
1778
1778

19
1 1 189019619 113958
2 800361853
1 422490453 494478 254349561
3
2 1152812283
2 1650380207
3
1 4033287043 23425848 3533684
2 2666277906
1 709388173 159264263 191915
3
2 3453785850
2 8487830948768
2 39677822722745
2 167837684014594
1 1534084935 1205975 21949299
1 151207136 41249553 693236
1 1121564684 68403 1385595730
3

254463518
254463517
254463516
1386594833

Hint

Sample Explanation #1

In the following images, the color of the nodes represents the time they were added.

The above image shows the tree after three $1$ operations ( 1 1 2 3, 1 6 2 2, and 1 7 1 4 ).

The above image shows the tree that has undergone two $2$ operations ( 2 12 and 2 13 ) based on the previous one.

The above image shows the tree that has undergone another $1$ operation ( 1 3 1 2 ) based on the previous one.

The above image shows the tree after two additional $2$ operations ( 2 7 and 2 3 ) based on the previous one.

The above image shows the tree that has undergone another $1$ operation ( 1 5 2 3 ) based on the previous one.

The above image shows the tree after all operations have been performed.

Constraints

For all test cases, it is guaranteed that:

• $1\le m\le 10^5$;
• The $x$ in the $1$ operation satisfies $1 \le x \le n$ and the $x$ node still exists on the tree, guaranteeing that $1 \le l, k \le 10^{18}$;
• The $x$ in the $2$ operation satisfies $1 \lt x \le n$ and the $x$ node still exists on the tree;
• At any given moment, $n$ satisfies $n \le 10 ^ {18}$.

Subtasks are used in this task.

• Subtask 0 (10 points): $k \le 5000$.
• Subtask 1 (20 points): $k \le 5 \times 10^5$.
• Subtask 2 (20 points): There is no $2$ operation.
• Subtask 3 (20 points): The value of $l$ in the $1$ operation is $1$.
• Subtask 4 (30 points): No further restrictions.