Banana Tree Blessings

You are given a rooted tree that initially consists of a single node with id \(1\) (the root) and a variable \(n = 1\). The tree will be modified by a sequence of operations. Each node has an associated depth defined as follows: the root has depth \(1\) and every other node has depth equal to its parent’s depth plus \(1\).

There are three types of operations:

1. Add Chain Operation: Given parameters \(x, l, k\) (presented on one line as x l k), attach \(k\) new chains, each of length \(l\), to node \(x\). For each chain, let the chain be \(v_1, v_2, \dots, v_l\). The edge \((x, v_1)\) is added first, then for each \(1 \le i < l\) an edge \((v_i, v_{i+1})\) is added. After this operation, the total number of nodes is increased by \(k \times l\). In formulas, if the current value of \(n\) is used to number the new nodes, then for each chain \(i\) from \(0\) to \(k-1\) and for each \(j=1\) to \(l\), a new node with id \(n + i\cdot l + j\) is added with depth \(\text{depth}(x) + j\).
2. Delete Subtree Operation: Given a single integer \(x\) on one line, delete node \(x\) and its entire subtree (i.e. \(x\) and all descendants of \(x\) are removed from the tree).
3. Query Operation: Given a line containing only a question mark ?, output the maximum frequency among the depths of all currently existing nodes. In other words, if for each depth \(d\) you count how many nodes have that depth, output the maximum count.

You are guaranteed that all operations are valid. Process the \(Q\) operations in order. For every query operation, output its answer according to the current state of the tree.

inputFormat

The input begins with an integer \(Q\) (the number of operations). Each of the next \(Q\) lines represents an operation in one of the following formats:

• x l k (three integers separated by spaces): a Add Chain Operation.
• x (a single integer): a Delete Subtree Operation.
• ? (a single question mark): a Query Operation.

It is guaranteed that the operations are valid.

outputFormat

For each query operation, output on a separate line the maximum frequency among all depths of the tree at that time. If the tree is empty, output \(0\).

sample

5
1 2 2
?
2
?
?

2
1
1