The key generation process for an asymmetric encryption algorithm is as follows:
- Choose two distinct prime numbers $p$ and $q$.
- Calculate $N = pq$ and $r = (p-1)(q-1)$.
- Select an integer $e$ such that $e < r$ and $\gcd(e, r) = 1$.
- Calculate an integer $d$ such that $ed \equiv 1 \pmod r$.
- The pair $(N, e)$ is called the public key, and the pair $(N, d)$ is called the private key.
When a message $n$ needs to be encrypted (assuming $n$ is an integer less than $N$, as any formatted message can be converted into an integer representation), use the public key $(N, e)$ and perform the operation: $$n^e \equiv c \pmod N$$ to obtain the ciphertext $c$.
To decrypt the ciphertext $c$, use the private key $(N, d)$ and perform the operation: $$c^d \equiv n \pmod N$$ to obtain the original message $n$. The proof of the algorithm's correctness is omitted.
Since ciphertext encrypted with a public key can only be decrypted with the corresponding private key and cannot be decrypted with the public key itself, it is called an asymmetric encryption algorithm. Typically, the public key is made public by the message recipient, while the private key is held by the recipient themselves. This allows anyone sending a message to encrypt it using the public key, while only the recipient can decrypt the message.
Your task is to find a feasible method to crack this encryption algorithm, i.e., to derive the private key from the public key and use it to decrypt the ciphertext.
Input
The input consists of a single line containing three space-separated positive integers $e, N, c$.
Output
The output consists of a single line containing two space-separated integers $d, n$.
Examples
Input 1
3 187 45
Output 1
107 12
Note 1
In the example, $p = 11, q = 17$.
Subtasks
For $30\%$ of the data, $e, N, c \leq 2^{20}$.
For $100\%$ of the data, $1 \leq e, N, c \leq 2^{62}, c < N$.