Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 150 点
問題文
MMNMMさんは夏祭りに出ていた N 次元石屋さんで N 次元の小石をたくさん買いました.
MMNMMさんはこの N 次元の小石をある正の整数 s について一辺 s の N 次元空間上の三角形状に積みます.ただし,小石を一辺 s の N 次元空間上の三角形状に積むとは,
- N 次元空間の格子点 (x_1, x_2, ... , x_N) であって, すべての i について x_i \geq 0 が成り立ち,かつ x_1 + x_2 + … + x_N < s が成り立つようなものすべてに1つずつ石を置くように石を積む
ことをいいます.
MMNMMさんは買った石で一辺 s_1 の N 次元空間上の三角形状に石がちょうど積めることがわかり,さらに一辺 s_2 の N-1 次元空間上の三角形状にもちょうど積めることがわかりました.
このとき, s_1 と s_2 (s_1 \neq s_2) としてありえる整数の組を一組出力してください.
ただし,MMNMMさんはか弱いプログラマーなので小石を 10^{100000} 個以上買うことはできず,狭い部屋に住んでいるので一辺 10^{18} 以上の三角形状に小石を積むことはできません.
制約
すべてのテストケースは以下の制約を満たします.
- 2 \leq N \leq 10^5
- MMNMMさんが買う小石の数が 10^{100000} 個未満であり, s_1 と s_2 がともに 10^{18} を超えないような解が存在することが保証されている.
入力
入力は以下の形式で標準入力から与えられる.
N
- 1行目には,整数 N が書かれている.これは,売られている小石が N 次元小石であり,MMNMMさんが N 次元および N-1 次元空間上の三角形状に小石を積んだことを表している.
出力
標準出力に,s_1 と s_2 としてありえる整数の組をこの順に空白を区切りとしてを1行に出力しなさい.
ただし,買う小石の数が 10^{100000} を, s_1 と s_2 が 10^{18} を超えてはならない.
入力例 1
2
出力例 1
10 55
一辺10の三角形状に石を並べると55個の石が必要で,これを一列に並べると一次元の三角形状になります.
入力例 2
3
出力例 2
20 55
どちらもちょうど1540個の石を使います.