Modular Reverse Engineering

Sometimes a competitive programming problem whose output is a rational number $\frac{p}{q}$ asks you to output the quantity $pq^{-1} \bmod m$ instead, for some prime modulus $m$. This quantity is hard to debug when your program gives the wrong answer, because computing $q^{-1}$ by hand is difficult and the value can be very large even for small rationals. For example, $1 \cdot 2^{-1} \bmod 97 = 49$.

To debug your solution quickly, you want to write a program that recovers $p$ and $q$ from $pq^{-1} \bmod m$. The possible values of $p$ and $q$ are not unique, but one piece of information narrows them down: $\frac{p}{q}$, read as an ordinary rational number, lies in the range $[x, x + 1)$ for some integer $x$.

Given the three values $v$, $x$, and $m$, find the minimum possible $p$ and the corresponding $q$ such that ($0 \leq p, q < m$) $pq^{-1} \equiv v \bmod m$ and $x \leq \frac{p}{q} < x + 1$.

The input is a single line with three space-separated integers $v$, $x$, and $m$, where $3 \leq m \leq 10^6$, $1 \leq v < m$, $0 \leq x < m$, and $m$ is prime.

Print the minimal integer $p$ and the corresponding $q$ such that $0 \leq p,q < m$, $pq^{-1} \equiv v \bmod m$, and $x \leq \frac{p}{q} < x + 1$. If several such pairs exist, print the pair with the minimum value of $p$. If no such $p$ and $q$ exist, print a single $-1$ instead.