P1797 [Template] Stern-Brocot Tree

This is a template problem. ([Source](https://judge.yosupo.jp/problem/stern_brocot_tree)) To help Xiaoyuan defeat the Witch’s Night, you need to answer queries on the Stern-Brocot tree.

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$.

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 $T$ lines, each containing the answer to the corresponding task, in the formats given in the Description.

- $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