List of Powers

Let $p$ be a prime number and $a$ an integer such that $0 < a < p$. Find all integers from $l$ to $r$ inclusive that can be written as $a^{k} \bmod p$ for some non-negative integer $k$. The number of such integers is at most $100$.

The only line contains four integers $p$, $a$, $l$, and $r$, separated by spaces. The constraints are $0 < a < p \le 10^{9}$, $p$ is prime, and $0 \le l \le r < p$.

Print all integers from $l$ to $r$ inclusive that can be written as $a^{k} \bmod p$ for some non-negative integer $k$, in ascending order. Separate consecutive integers by spaces. The input is guaranteed to have at most $100$ such integers.

Since $p$ is prime and $0 < a < p$, $a$ is not a multiple of $p$, so $a^{k} \bmod p$ is never $0$. The values of $a^{k} \bmod p$ repeat in a cycle as $k$ grows.