ストーリー

RSA 暗号は、世界で広く使われている公開鍵暗号アルゴリズムです。

高橋くんは自分でも RSA 暗号を使ってみようと思いました。

そのためには鍵を作ることが必要です。

RSA 暗号の鍵生成は以下のような手順で行います。

鍵生成

RSA 暗号では、鍵を生成するために適当な素数 $p, q$ と、自然数 $e$ を選びます。

自然数 $n$ を、

• $n = pq$

と置きます。

ここで、 $\varphi = \phi(n) = (p - 1)(q - 1)$ とすると、 $e$ は $\varphi$ 未満の自然数で、 $\varphi$ と互いに素である必要があります。（ $\phi(n)$ はオイラーのφ関数 ）

自然数 $d$ を、

• $d \equiv e^{-1} \mod \varphi$

と置きます。

$\varphi$ は多くの場合合成数であるため、 $d$ の計算は（拡張）ユークリッドの互除法により行います。

このようにして計算された値を使い、公開鍵と秘密鍵を作成することができます。

• 公開鍵: $(n, e)$
• 秘密鍵: $(n, d)$

問題文

相異なる素数 $p, q$ と正整数 $e$ が与えられます。

秘密鍵 $(n, d)$ を生成し、 $n$ と $d$ を出力してください。

ただし、 $n = pq$ とし、 $d$ を $d \equiv e^{-1} \mod (p - 1)(q - 1)$ となるような最小の非負整数とします。

制約

• $2 \le p, q \le 10^9$
• $p, q$ は素数であり、 $p \ne q$ である
• $2 \le e \le (p - 1)(q - 1)$
• $e$ と $(p - 1)(q - 1)$ は互いに素である
• 入力はすべて整数である

入力

出力

• $1$ 行目に $n$ を出力せよ。
• $2$ 行目に $d$ を出力せよ。

入出力例

5 11 3

55
27

$p = 5, q = 11, e = 3$ のとき、 $n = 55, d = 27$ となります。

97 997 64295

96709
10007

998244353 998244853 5

996492287418565109
199298457084415181

出力は $32$ ビット整数で表される範囲を超える可能性があります。