Description

Conventions:

• In this problem, all fractions in the input/output must be in lowest terms.
• In this problem, every input fraction $\dfrac{p}{q}$ satisfies $1 \le p,q \le 10^9$.

Task 1: ENCODE_PATH

• Input format: ENCODE_PATH $p$ $q$;
• Output format: $k$ $n_1$ $c_1$ $n_2$ $c_2$ $\cdots$ $n_k$ $c_k$.

Given a fraction $\dfrac{p}{q}$, output the path from the root of the Stern-Brocot tree to the node $\dfrac{p}{q}$ in the following format:

$k$ $n_1$ $c_1$ $n_2$ $c_2$ $\cdots$ $n_k$ $c_k$

Here $c_i \in \{\texttt{L}, \texttt{R}\}$ means go to the left or right child, and $n_i$ is how many times to repeat $c_i$. You must ensure $\forall 1 \le i < k$, $c_i \ne c_{i+1}$.

Task 2: DECODE_PATH

• Input format: DECODE_PATH $k$ $n_1$ $c_1$ $n_2$ $c_2$ $\cdots$ $n_k$ $c_k$;
• Output format: $p$ $q$.

Given a path from the root in the same format as in Task 1, output the fraction on that node. It is guaranteed that the answer satisfies $1 \le p,q \le 10^9$.

Task 3: LCA

Given $\dfrac{a}{b}$ and $\dfrac{c}{d}$, output the fraction $\dfrac{p}{q}$ on the LCA of $\dfrac{a}{b}$ and $\dfrac{c}{d}$.

• Input format: LCA $a$ $b$ $c$ $d$;
• Output format: $p$ $q$.

Task 4: ANCESTOR

Given $\dfrac{a}{b}$ and $k$, output the value $\dfrac{p}{q}$ of the node whose depth is $k$ on the chain from $\dfrac{a}{b}$ up to the root. If it does not exist, output $-1$.

• Input format: ANCESTOR $k$ $a$ $b$;
• Output format: $p$ $q$.
• Constraints: $1 \le k \le 10^9$.

Task 5: RANGE

Given $\dfrac{p}{q}$, let $S$ be the set of all fractions in the subtree of $\dfrac{p}{q}$ in the Stern-Brocot tree. Output $\inf S = \dfrac{a}{b}$ and $\sup S = \dfrac{c}{d}$.

In particular, for $0$, output $0$ $1$; for $+\infty$, output $1$ $0$.

• Input format: RANGE $p$ $q$;
• Output format: $a$ $b$ $c$ $d$.

Input Format

The first line contains a positive integer $T$, the number of test cases.

Each of the next $T$ lines describes one task, in the formats given in the Description.

Output Format

Output $T$ lines, each containing the answer to the corresponding task, in the formats given in the Description.

10
DECODE_PATH 0
DECODE_PATH 3 R 2 L 1 R 2
ENCODE_PATH 1 1
ENCODE_PATH 5 11
LCA 2 3 3 5
LCA 5439 19294 8291 29410
ANCESTOR 10 1 1
ANCESTOR 300 1000000000 1
RANGE 1 1
RANGE 11 8

1 1
11 4
0
2 L 2 R 4
2 3
148 525
-1
301 1
0 1 1 0
4 3 7 5

Hint

• $1 \le T \le 10^5$.
• All input fractions are in lowest terms.
• Every input fraction $\dfrac{p}{q}$ satisfies $1 \le p,q \le 10^9$.

Translated by ChatGPT 5