The Grand Combat Delusion movie was so bad that quite a
few party guests have decided to leave. Thus there aren’t
enough people left to stop Atli from selecting the next thing
to watch. He puts on his favourite show,
Hydrationsword
Saga. As time passes Atli begins to talk more and more
about the show while it’s going on, leaving little left to be
spoiled. He talks at length about the main character’s battle
with Angrygon at their side against the dark god and Angrygon’s
tragic fate in that battle. He continues babbling, going on and
on about the Futon-brothers and their mechs and the AB knight
and his fall to the dark side. At this point the group in front
of the television is starting to thin quite a bit, but this
does not stop Atli. He keeps talking, moving next on to the red
scythe, the AB knight’s lackeys and the unforgettable fight
when the main character temporarily fell over to the darker
side. He then moves on to talk about the battle between the
main character and the AB knight and the main character’s
eventual victory. But Atli then adds that this is not all,
there is yet more to be said. Only the most patient of party
guests were still listening, but he told them of the battle
against VaurSala and how everyone came together in the end to
defeat this might enemy and how much they lost on the way
there. Not before long Atli finds himself speaking to an empty
room, so he pauses the show. He looks around and sees that
everyone has left. He figures he should probably get gong as
well then, but on his way home he thinks about the lecture he
has to get ready for the competitive programming course. His
mind wanders to Floyd’s cycle finding algorithm. ‘What would be
a good problem to test people’s understanding of that
algorithm?’ he thinks to himself. ‘I have to come up with some
interesting function to test it on’ he thinks next. When he
finally gets into bed, inspiration strikes. ‘Aha!
$f(x) = ax^ b$ will do nicely!’ he
thinks before falling asleep. The following day he gets working
on the problem. But then he realizes that he has to prepare
testing data and a solution to the problem. Since he is too
lazy to program he will need your assistance.
Given three numbers $a, b,
m$ the assignment is to run Floyd’s cycle finding
algorithm on the function $f(x) =
ax^ b (\textrm{mod} \ m)$. Let $f^{[n]}(x)$ denote applying
$f$ exactly $n$ times on $x$. Running Floyd’s algorithm thus
means we want to find the smallest $\mu $ such that $f^{[\mu ]}(x) = f^{[\lambda + \mu
]}(x)$ for all $x$
and some $\lambda > 0$.
For this particular $\mu $
one is also to determine the smallest such $\lambda $. $\mu , \lambda $ should then be
printed.
Input
The only line in the input contains three integers
$a, b, m$ satisfying
$0 \leq a, b \leq 10^{15}$
and $1 \leq m \leq
10^{15}$.
Output
Print $\mu $ and
$\lambda $ on a single
line with a single space between the numbers.
Sample Input 1 |
Sample Output 1 |
2 3 17
|
0 4
|
Sample Input 2 |
Sample Output 2 |
5 7 35
|
1 6
|