Description

You are given a tree that initially has only one root node $1$. You need to process the following two types of operations:

• path u s means that $s$ nodes are added one by one under node $u$: the $i$-th added node is the child of the $(i-1)$-th added node $(2 \le i \le s)$. In particular, the first added node is a child of $u$. Suppose that before adding, the maximum node label in the tree is $n$. Then the $s$ new nodes will be labeled consecutively as $n+1, n+2, \cdots, n+s$.
• dig u v asks for the midpoint of $u$ and $v$. Formally, let the distance between $u$ and $v$ be $d$. You need to output the label of the node on the path from $u$ to $v$ whose distance from $u$ is $\left\lfloor \frac d2 \right\rfloor$.

Input Format

This is an interactive problem. First, you need to read the number of operations $n$ from standard input.
Then, for the next $n$ operations, you will receive one of the following two command formats:

• P u s represents one path u s operation.
• D u v represents one dig u v operation.

For the first type, you do not need to output anything. For the second type, you must output the answer and flush the output buffer before you can read subsequent operations.

After you output a line, please flush the buffer:

• In C++, use fflush(stdout) or cout.flush().
• In Pascal, use flush(output).
• In Python, use stdout.flush().
• For other languages, please check the documentation.

Output Format

For each D u v operation, output one line containing the answer. It is guaranteed that there is at least one such operation.

11
P 1 2
D 1 3
P 2 5
D 7 3
D 3 7
P 1 2
P 3 3
D 10 11
P 5 1
D 14 8
D 2 4

2
5
4
1
6
2

Hint

For $20\%$ of the testdata, the maximum node label in the final tree does not exceed $5000$, and $n \le 5000$.
For $50\%$ of the testdata, the maximum node label in the final tree does not exceed $400\ 000$.
For $100\%$ of the testdata, the maximum node label in the final tree does not exceed $10^9$, and $n \le 400\ 000$.

Notes

This problem is translated from CEOI 2011 day 1 T3 Treasure Hunt。

Translated by ChatGPT 5