TopCoder

User's AC Ratio

70.0% (21/30)

Submission's AC Ratio

39.4% (54/137)

Description

約瑟先生在傍晚時刻總是東奔西跑地,邀請親朋好友到家裡共進晚餐。 約瑟先生住的是豪宅,每到了晚餐時刻,豪宅內總是人山人海。 剛回到家的約瑟先生,急切的想要尋找他的太太,傭人也幫忙尋找,於是他們在庭院和人群中不斷的喊著: 「約瑟夫人咧?」

好啦,我承認上面的冷笑話不好笑= =。(逃~)

我們現在關心的是晚餐。噢,不是的,我們關心的是約瑟夫問題。


約瑟先生和他的親朋好友在大樹底下圍成一圈,並且從某一位親友開始,順時針報數(從1號開始報),每數k個人,那位親友就必須退場,排到一旁,而順位的下一個人,就從1號開始報數,繼續循環,直到剩下M個人為止。

最後剩下的那M個人可以先開動,大家要在旁邊「看」到他們吃飽…


由於親友們實在是太多了,每次剩下M個人的時候,大家早已餓昏,卻又只能眼巴巴的看著最後剩下的人開動。
約瑟先生也是如此。因此,他想要儘可能的成為最後剩下的人們之一,這樣才對得起自己的五臟廟。

你的工作,就是幫約瑟先生計算出:N個人,每K個一數的時候,站在第一個報數的人順時針方向上的哪個位置,才可以先開動?

當然,由於你也在約瑟先生的邀請之列,你偶爾想要耍一下約瑟先生。
你修改了一下你的程式,使得幫約瑟先生算出的位置,剛好在晚餐前最後一輪被刷掉(嘿嘿,夠心機吧!)

例如上面的兩張圖,N=7,K=3,M=3,那麼被刷掉的人的位置依序是3,6,2,7,讓約瑟先生排在位置7讓他出糗吧
事後只要跟他說:啊,程式算錯了~就好了!放心,約瑟夫人很好的。

由於太心機了,約瑟先生決定不再請你幫忙寫程式。(當然,你還是有晚餐吃XD)
不過約瑟夫人倒是對這個很有興趣,於是跟你伸程式碼。

請你幫約瑟夫人寫一個程式吧XD

Input Format

輸入可能包含多筆測試資料。每一筆測試資料代表某個晚上的晚餐情形,佔一列,包含三個正整數N,K,M。
(1<=M<N<=1,000,000,000;1<=K<=10,000)
當N=K=M=0的時候代表輸入結束。

Output Format

對於每筆測試資料,請輸出使約瑟先生當天晚上會餓肚子並且出糗的絕佳位置。

Sample Input

5 3 2
5 3 4
0 0 0

Sample Output

5
3

Hints

第一筆測試資料中,退場者依序為位置3,1,5。於是位置5成了絕佳位置。

Problem Source

原TIOJ1203 / TIOJ 2008例行賽02 (prob E)。Problem Setter:Tmt。

Subtasks

No. Testdata Range Score
1 0 50
2 1 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 3000 65536 262144 1
1 3000 65536 262144 2