Path Between Two Preorder-Indexed Nodes in a Fibonacci Tree (Without Building the Tree)

Problem: Path Between Two Preorder-Indexed Nodes in a Fibonacci Tree (Without Building the Tree) 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) consists of a single node. T(2) consists of a single node. For k ≥ 3, T(k) is a tree whose root has: left subtree T(k-1) right subtree T(k-2) Let size(k) be the number of nodes in T(k). Then: size(1) = 1 size(2) = 1 size(k) = 1 + size(k-1) + size(k-2) for k ≥ 3 All nodes of T(k) are numbered in preorder (root, then left subtree, then right subtree), using 1-based indices from 1 to size(k). You are given: an integer k with 1 ≤ k ≤ 60 two integers a and b such that 1 ≤ a, b ≤ size(k), representing two node indices in the preorder numbering of T(k) The tree can be extremely large for big k, so you must not construct the tree explicitly. Task Implement: List<Long> pathInFibonacciTree(long k, long a, long b) Return the sequence of node indices (in preorder numbering of T(k)) along the simple path from node a to node b. The path must start with a and end with b. All indices in the returned list are preorder indices in T(k). Constraints k ≤ 60, so size(k) can be very large and must be handled with 64-bit integers. You must locate nodes and compute the path using only the recursive structure and subtree sizes (interval arithmetic), without building explicit nodes. Example Input 3 1 1 Output 1