Background

I want to plant a banana tree, and hang all my blessings upon it.

Description

Little C likes to plant trees.

He planted a banana tree, but this tree seems to require manual maintenance to grow.

Therefore, he often hangs some "blessings" at a certain position on the tree. A "blessing" is essentially a chain.

Sometimes, a part of the tree grows too well, causing the entire tree to grow crooked, so he has to cut off a part of it.

Little C also likes modes, so he will often ask you for the maximum frequency of any depth among all nodes in the tree.

Specifically, there is a rooted tree, initially containing only the root node $1$, and there is a variable $n=1$.

There are three types of operations:

1. x l k: Add nodes numbered $n+1 \sim n+lk$ and edges $(x, n+1), (n+1, n+2), \dots, (n+l-1, n+l)$; $(x, n+l+1), (n+l+1, n+l+2), \dots, (n+2l-1, n+2l)$; $\dots$; $(x, n+(k-1)l+1), (n+(k-1)l+1, n+(k-1)l+2), \dots, (n+kl-1, n+kl)$. That is, hang $k$ chains of length $l$ under node $x$. After this operation, $n \gets n+kl$.
2. x: Delete node $x$ and its subtree.
3. (No parameters): Query the maximum frequency of any depth among all nodes in the tree.

Input

The first line contains an integer $m$, representing the number of operations.

The next $m$ lines each contain several integers. The first integer $op$ represents the type of the current operation, and the subsequent inputs correspond to the formats described above.

Output

For each operation of type $3$, output one integer per line representing the answer.

Examples

Input 1

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

Output 1

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

Note 1

In the figures below, the color of the nodes represents the time they were added.

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

The figure above shows the tree after two type $2$ operations (2 12 and 2 13) on the previous state.

The figure above shows the tree after one type $1$ operation (1 3 1 2) on the previous state.

The figure above shows the tree after two type $2$ operations (2 7 and 2 3) on the previous state.

The figure above shows the tree after one type $1$ operation (1 5 2 3) on the previous state.

The figure above shows the tree after all operations.

Input 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

Output 2

3
6
8
12
11
7
8
1000000001

Input 3

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

Output 3

902
1257
1257
1415
1778
1778

Input 4

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

Output 4

254463518
254463517
254463516
1386594833

Constraints

For all test data, it is guaranteed that:

• $1 \le m \le 10^5$;
• In operation $1$, $x$ satisfies $1 \le x \le n$ and node $x$ still exists in the tree; $1 \le l, k \le 10^{18}$;
• In operation $2$, $x$ satisfies $1 < x \le n$ and node $x$ still exists in the tree;
• At any time, $n \le 10^{18}$.

This problem uses bundled testing.

Let $K$ be the maximum value of $n$ during the operations.

• Subtask 1 (10 points): $K \le 5000$.
• Subtask 2 (20 points): $K \le 5 \times 10^5$.
• Subtask 3 (20 points): No type $2$ operations.
• Subtask 4 (20 points): The value of $l$ in type $1$ operations is $1$.
• Subtask 5 (30 points): No special restrictions.