Middle of the Path

We are given a tree with a single node—the root, initially labeled \(1\). You need to process two types of operations:

• path u s: Under node \(u\), add a chain of \(s\) nodes. Specifically, the first new node becomes a child of \(u\) and each subsequent node is added as a child of the previous new node. Let \(n\) be the maximum node number in the tree before the addition; then the new nodes are sequentially labeled \(n+1, n+2, \ldots, n+s\).
• dig u v: Query the middle node on the unique path from \(u\) to \(v\). Formally, let the distance between \(u\) and \(v\) be \(d\); you must output the node on the path from \(u\) to \(v\) that is at distance \(\lfloor\frac{d}{2}\rfloor\) from \(u\).

It is guaranteed that all operations are valid.

inputFormat

The first line contains an integer (Q) representing the number of operations. Each of the following (Q) lines contains an operation in one of the following formats:

path u s dig u v

For a path operation, (u) and (s) are integers. For a dig operation, (u) and (v) are integers.

outputFormat

For each dig operation in the input, output a single line containing the answer—the node number located at distance (\lfloor\frac{d}{2}\rfloor) from (u) on the path to (v), where (d) is the distance between (u) and (v).

sample

5
path 1 3
dig 1 4
path 2 2
dig 3 5
dig 4 6

2
2
2