Problem - Planets Queries I

You are given $n$ planets where each planet has a teleporter to another planet. Answer $q$ queries: starting from planet $x$, where are you after $k$ steps? $k$ can be up to $10^9$. This is the direct application of binary lifting. Each planet is a node, and the teleporter defines $f(x)$.

Simulating $10^9$ steps times out. I'll show you how to build the jump table and answer queries efficiently. The preprocessing takes $O(n \log n)$, but each query is $O(\log k)$.

Space complexity is $O(n \log n)$ for the data structures used.