Hide

Problem A
Shanks' Baby Step Giant Step

Languages en is

Implement the baby-step giant-step algorithm to solve $g^x \equiv h \pmod{p}$ for $x$.

Input

Input is three lines. The first line contains the prime $p$ where $3 \leq p < 2^{40}$. The second line contains the integer $g$ where $2 \leq g < p$ of order at least 2. The third line contains the integer $h$ where $0 \leq h < p$.

Output

Output one line with any valid solution $0 \leq x < p - 1$ or no solution if no solution exists.

Sample Input 1 Sample Output 1
367
2
137
75
Sample Input 2 Sample Output 2
367
2
179
no solution