acm International Collegiate Programming Contest

Links

A B C D E F G H

Problem E

マラソンを観よう

陸上競技ファンのあなたは,とあるマラソンの大会を現地で観戦することにした.この大会では,XY 平面上の原点と点 (a, b) を結ぶ線分上がマラソンコースとなる.また,大会中の交通規制のため,大会の観戦は,X 座標と Y 座標がともに整数である点のうち,マラソンコース上にない点のみで行うことができる.

あなたは,もちろん,できるだけマラソンコースに近い地点で大会を観戦したい.上述の条件を満たす点のうち,マラソンコースまでのユークリッド距離が最も近い点を求めよ.ただし,そのような点が複数ある場合には,その中で X 座標が最も小さい点を求めよ.さらにそのような点が複数ある場合には,その中で Y 座標が最も小さい点を求めよ.

Input

入力は 300,000 個以下のデータセットからなる.各データセットは次の形式で表される.

a b

a, b はともに 1 以上 109 以下の整数であり,マラソンコースの一方の端点の座標を表す.

入力の終わりは 2 つのゼロからなる行で表される.

Output

各データセットに対し,あなたがこのマラソン大会を観戦するのに最適な地点の X 座標と Y 座標を,空白区切りで一行に出力せよ.

Sample Input

2 3
2 9
7 2
9 8
4 9
6 6
5 7
9 1
5 3
65537 735134400
0 0

Sample Output

1 1
1 4
3 1
1 1
1 2
0 1
2 3
1 0
2 1
23788 266832127
(End of Problem E) A B C D E F G H