Skyscraper MinatoHarukas

時間制限 : 8 sec, メモリ制限 : 262144 KB
英語版はこちら

超高層ビル「みなとハルカス」

ポルト氏は, 1 ギガ階建ての新超高層ビル「みなとハルカス」の何フロアかをオフィスとして賃借し, 新規事業を始める計画だ. 彼は縦方向に連続するなるべく多くのフロアを借りることを要求する. というのは,できるだけ多くの縦に連続した窓に広告を掲示したいのだ. フロアの月額賃料は階数に比例しており, n 階のフロアの賃料は, 1 階の賃料の n 倍である. なお,ここでは地下のフロアは賃借対象外である. ポルト氏を助けるため,あなたには, 月額賃料の総額がポルト氏の予算と ちょうど一致 し, かつ, ポルト氏の要求を満たす縦方向に連続するフロアを見つけるプログラムを書いてほしい.

例えば,予算が 1 階の賃料を単位として 15 単位のときは,4 通りの借り方がある. 1+2+3+4+5, 4+5+6, 7+8, そして 15 である.いずれもその和が 15 になる. もちろんこの場合のフロア数最大の賃借は 1+2+3+4+5 の賃借, すなわち,1 階から 5 階までの賃借である.

Input

入力は複数のデータセットからなる. 各データセットは次の形式で表される.

b

データセットは 1 行からなり, ポルト氏の予算が 1 階の賃料の倍数 b として与えられる. b は正の整数であり, 1 < b < 109 を満たす.

入力の終わりは, 1 個のゼロだけからなる行で表される. データセットの総数は 1000 を超えない.

Output

各データセットについてそれぞれ 1 行に, ポルト氏の予算にちょうど一致するように 縦方向に隣接するできるだけ多くのフロアを賃借するやり方を表すふたつの正整数を出力せよ. ひとつ目はフロアのうち最下層の階数,ふたつ目はフロアの総数とせよ.

Sample Input

15
16
2
3
9699690
223092870
847288609
900660121
987698769
999999999
0

Output for the Sample Input

1 5
16 1
2 1
1 2
16 4389
129 20995
4112949 206
15006 30011
46887 17718
163837 5994

Source: ACM International Collegiate Programming Contest , Japan Domestic Contest, Yokohama, Japan, 2018-07-6
https://icpc.iisf.or.jp/2018-yokohama/