  We study a random walk on a point process given by an ordered array of points
$(\omega_k, \, k \in \mathbb{Z})$ on the real line. The distances $\omega_{k+1}
- \omega_k$ are i.i.d. random variables in the domain of attraction of a
$\beta$-stable law, with $\beta \in (0,1) \cup (1,2)$. The random walk has
i.i.d. jumps such that the transition probabilities between $\omega_k$ and
$\omega_\ell$ depend on $\ell-k$ and are given by the distribution of a
$\mathbb{Z}$-valued random variable in the domain of attraction of an
$\alpha$-stable law, with $\alpha \in (0,1) \cup (1,2)$. Since the defining
variables, for both the random walk and the point process, are heavy-tailed, we
speak of a L\'evy flight on a L\'evy random medium. For all combinations of the
parameters $\alpha$ and $\beta$, we prove the annealed functional limit theorem
for the suitably rescaled process, relative to the optimal Skorokhod topology
in each case. When the limit process is not c\`adl\`ag, we prove convergence of
the finite-dimensional distributions. When the limit process is deterministic,
we also prove a limit theorem for the fluctuations, again relative to the
optimal Skorokhod topology.
