You are given a special family of binary trees called **Fibonacci trees**. The `k`‑th order Fibonacci tree `T(k)` is defined recursively: - `T(1)` is a single node. - `T(2)` is a single node. - For `k ≥ 3`, `T(k)` is a tree whose root has: - left subtree `T(k − 1)` and - right subtree `T(k − 2)`. Let `size(k)` be the number of nodes in `T(k)`. You can compute `size(k)` from the definition above: - `size(1) = 1` - `size(2) = 1` - `size(k) = 1 + size(k − 1) + size(k − 2)` for `k ≥ 3` Now, imagine we **number** the nodes of `T(k)` in **preorder** (root, then left subtree, then right subtree), using **1‑based indices** from `1` to `size(k)`. You are given: - An integer `k` (the order of the Fibonacci tree), with `1 ≤ k ≤ 60`. - Two integers `a` and `b`, such that `1 ≤ a, b ≤ size(k)`; these are **indices** of two nodes in the preorder numbering of `T(k)`. The tree can be **very large** for big `k`, so you **must not** construct it explicitly in memory. ### Task Design and implement a function: ```text List<Long> pathInFibonacciTree(long k, long a, long b) ``` that returns the **sequence of node indices** (in preorder numbering) along the simple path from node `a` to node `b` in `T(k)`. - The path should start with `a` and end with `b`. - Indices in the returned list should be the preorder indices in `T(k)`. Constraints and requirements: - `k` can be as large as 60 (or similar), so `size(k)` may be large (up to around 10^12). Use 64‑bit integers for sizes and indices. - You must treat the tree **implicitly**: - Use the recursive structure and the sizes of subtrees to navigate. - You may not allocate `O(size(k))` memory or explicitly build all nodes. - Aim for an algorithm with time complexity **polylogarithmic or at worst O(h)**, where `h` is the height of the tree (proportional to `k`), i.e., `O(k)` or similar. ### Hints / clarifications - Because of the preorder layout, for `T(k)`: - The root always has index `1` in its own tree. - The left subtree `T(k − 1)` occupies indices `[2, 1 + size(k − 1)]` in `T(k)`. - The right subtree `T(k − 2)` occupies the following range after that. - You may find it helpful to implement helper functions that, given `(k, indexRange, nodeIndex)`, determine whether the node lies in the left subtree, right subtree, or is the root. Design your algorithm and helper functions so that you can: 1. Compute the path from each node up to the root (in terms of indices) without building the tree. 2. Combine these paths to construct the path from `a` to `b` via their lowest common ancestor (LCA). Return the final path as a list of preorder indices.