Core Idea - Preprocessing Once

Building the jump table takes $O(n \log n)$ time. With $q$ queries, total time is $O(n \log n + q \log k)$. The preprocessing is done once, then you answer all queries. If you simulate each query, total time is $O(qk)$. When $k$ is large and $q$ is large, simulation times out.

Binary lifting is the only way. Preprocessing pays off when you have multiple queries. The first query might feel expensive, but amortized cost per query is $O(\log k)$. This amortization is common in competitive programming.