Joseph's Potato

Time Limit : 1 sec, Memory Limit : 65536 KB

ヨセフのおイモ


昔、ヨセフのおイモというゲームがありました。n 人が参加しているとしましょう。参加者は中心を向いて円陣を組み、1 から順番に番号が振られます。アツアツのおイモがひとつ、参加者 n (左の図内側の大きい数字の 30 )に渡されます。おイモを渡された参加者は右隣の参加者にそのおイモを渡します。 m 回目に渡された人は右隣の人に渡して円陣から抜けます(左の図では m = 9 の場合を表しています) 。 回渡す毎に一人ずつぬけ、最後に残った人が勝者となり、おイモをいただきます。

n ,m が決まってから、実際におイモを渡し始める前にどこにいたら勝てるかわかるといいですよね。上の図は 30 人の参加者で 9 人ごとに抜けるというルールでこのゲームをした場合を書き表しています。内側の大きい数字が参加者に振られた番号、外側の小さい数字が抜ける順番です。それによると、9,18,27,6,16,26 という順番で円陣から抜け出し、最後には 21 が残ることになります。すなわち 21 が勝者となります(小さい数字が 30 になっています)。

ゲーム参加者数 n と円陣から抜け出す参加者の間隔 m を入力し、勝者の番号を出力するプログラムを作成してください。ただし、m, n < 1000 とします。

入力

複数のデータセットが与えられます。各データセットは以下の形式で与えられます。

n m

ゲーム参加者数 n (整数)と円陣から抜け出す参加者の間隔 m (整数)が空白区切りで1行に与えられます。

入力は2つの 0 で終わります。データセットの数は 50 を超えません。

出力

各データセットに対して、勝者となりおイモをいただく人の番号(整数)を1行に出力してください。

Sample Input

41 3
30 9
0 0

Output for the Sample Input

31
21

Source: PC Koshien 2005 , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2005
(extended format)
http://www.pref.fukushima.jp/pc-concours/