Stern-Brocot Tree Operations

This problem involves several operations on the Stern–Brocot tree. All fractions in the input and output are in their simplest (reduced) form. In this problem, every fraction \(\frac{p}{q}\) satisfies \(1 \le p, q \le 10^9\).

There are five tasks:

Task 1: ENCODE_PATH

• Input: ENCODE_PATH p q
• Output: k n1 c1 n2 c2 ... nk ck

For a given fraction \(\frac{p}{q}\), you need to output the path from the root of the Stern–Brocot tree (which is \(\frac{1}{1}\)) to the node corresponding to \(\frac{p}{q}\). The path is encoded as groups: each group consists of a number \(n_i\) and a character \(c_i \in \{L,R\}\), meaning that the edge in that group is repeated \(n_i\) times. It is guaranteed that consecutive groups have different directions, i.e. \(c_i \neq c_{i+1}\) for all \(1 \le i < k\).

Task 2: DECODE_PATH

• Input: DECODE_PATH k n1 c1 n2 c2 ... nk ck
• Output: p q

Given a path (with the same format as in Task 1) starting from the root \(\frac{1}{1}\), output the fraction at that node.

Task 3: LCA

• Input: LCA a b c d representing fractions \(\frac{a}{b}\) and \(\frac{c}{d}\)
• Output: p q representing the fraction at the lowest common ancestor (LCA) of the two given fractions in the tree.

Task 4: ANCESTOR

• Input: ANCESTOR k a b where \(\frac{a}{b}\) is a node in the tree and \(k\) is a level (depth) on the path from the root \(\frac{1}{1}\) to \(\frac{a}{b}\). The root is considered at depth 1.
• Output: p q as the fraction at depth \(k\) on the unique chain from the root to \(\frac{a}{b}\). If such an ancestor does not exist, output -1.

Task 5: RANGE

• Input: RANGE p q
• Output: a b c d where \(\frac{a}{b}\) and \(\frac{c}{d}\) are, respectively, the infimum and supremum of the set \(S\) of all fractions in the subtree of \(\frac{p}{q}\) in the Stern–Brocot tree.
  Special cases: If the value is 0, output 0 1; if it is \(+\infty\), output 1 0.

Note on Implementation: For Tasks 1, 4, and 5, it is useful to derive the path from the fraction using an algorithm analogous to the Euclidean algorithm. In particular, for a fraction \(\frac{p}{q}\):

• If \(p < q\): then the next moves will be 'L' and you can compute the number of consecutive moves as \(n = \lfloor (q-1)/p \rfloor.
• If \(p > q\): then the next moves will be 'R' with \(n = \lfloor (p-1)/q \rfloor.
• Stop when \(p = q = 1\) (i.e. when you reach the root \(\frac{1}{1}\)).

For Tasks 2 and 4, simulate the navigation from the root by maintaining two boundaries \(L = \frac{0}{1}\) and \(R = \frac{1}{0}\). When moving left, update \(R := L + R\) (i.e. \(\frac{L_{num}+R_{num}}{L_{den}+R_{den}}\)); when moving right, update \(L := L + R\). The fraction at the current node is then \(\frac{L_{num}+R_{num}}{L_{den}+R_{den}}\).

For Task 3, a binary search using the mediant of the current boundaries can be performed: starting with \(L = \frac{0}{1}\) and \(R = \frac{1}{0}\), compute \(M = L+R\). If both given fractions are less than \(M\), update \(R = M\); if both are greater than \(M\), update \(L = M\); otherwise, \(M\) is the LCA.

For Task 5, after obtaining the encoding path for \(\frac{p}{q}\), use the simulation as in Task 2 to reach the node while maintaining the boundaries \(L\) and \(R\). These boundaries become the infimum and supremum (in reduced form) of the subtree \(S\).

inputFormat

The first token of input is one of the commands: ENCODE_PATH, DECODE_PATH, LCA, ANCESTOR, or RANGE. The rest of the tokens are integers and characters according to the task as described above.

outputFormat

Output the result in the format specified for each task.

sample

ENCODE_PATH 2 5

2 2 L 1 R