D - パスカルの三角形

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君は、パスカルの三角形が大好きです。

パスカルの三角形とは、一つ上の数字の、右上の数と左上の数を足した数を書き連ねていくことにより、表現することが出来る三角形です。

パスカルの三角形のy 段目は y 個の数で構成されており、 y 段目 x 番目の数を f(y,x) とすると、

  • x = 1、または x = y の時、f(y,x) = 1
  • それ以外の時、f(y,x) = f(y-1,x) + f(y-1,x-1)

と定義されます。

高橋君は、ある整数 A が、パスカルの三角形に含まれるかどうかを調べたいと思いました。

もし、パスカルの三角形に A が現れるのであれば、その段数、及び何番目かを出力し、出現しないのであれば、-1 -1と出力しなさい。


入力

入力は以下の形式で標準入力から与えられる

A
  • 1 行目には、整数 A(1 ≦ A ≦ 10^9) が与えられる。

出力

もし、パスカルの三角形に A が現れるのであれば、その段数、及び何番目かをスペース区切りで出力せよ。出現しないのであれば、-1 -1と出力せよ。出力の末尾には改行をいれること。

なお、出力は、どちらの数字も 2 × 10^9 以下の 整数でなければならない。


入力例1

10

出力例1

6 3

6 段目、 3 番目の数字は 10 です。他に 6 段目 4 番目なども条件を満たしますが、どの出力をしても問題ありません。


入力例2

3921225

出力例2

101 5

ある程度大きな数字が入力されることもあります。