Problems
And Then There Was One
And Then There Was One
Let’s play a stone removing game.
Initially, \textbf{n} stones are arranged on a circle and numbered \textbf{1}, ..., \textbf{n} clockwise (\textit{\textbf{Figure 1}}). You are also given two numbers \textbf{k} and \textbf{m}. From this state, remove stones one by one following the rules explained below, until only one remains. In step \textbf{1}, remove stone \textbf{m}. In step \textbf{2}, locate the \textbf{k}-th next stone clockwise from \textbf{m} and remove it. In subsequent steps, start from the slot of the stone removed in the last step, make \textbf{k} hops clockwise on the remaining stones and remove the one you reach. In other words, skip \textbf{(k−1)} remaining stones clockwise and remove the next one. Repeat this until only one stone is left and answer its number.
For example, the answer for the case \textbf{n = 8}, \textbf{k = 5}, \textbf{m = 3} is \textbf{1}, as shown in \textit{\textbf{Figure 1}}.
\includegraphics{https://static.e-olymp.com/content/5d/5dac1f55b6ce75b92cfdaf2fe3351cb33333df5c.jpg}
\textit{\textbf{Figure 1}}: An example game
\textbf{Initial state}: Eight stones are arranged on a circle.
\textbf{Step 1}: Stone \textbf{3} is removed since \textbf{m = 3}.
\textbf{Step 2}: You start from the slot that was occupied by stone \textbf{3}. You skip four stones \textbf{4}, \textbf{5}, \textbf{6} and \textbf{7} (since \textbf{k = 5}), and remove the next one, which is \textbf{8}.
\textbf{Step 3}: You skip stones \textbf{1}, \textbf{2}, \textbf{4} and \textbf{5}, and thus remove \textbf{6}. Note that you only count stones that are still on the circle and ignore those already removed. Stone \textbf{3} is ignored in this case.
\textbf{Steps 4--7}: You continue until only one stone is left. Notice that in later steps when only a few stones remain, the same stone may be skipped multiple times. For example, stones \textbf{1} and \textbf{4} are skipped twice in step \textbf{7}.
\textbf{Final State}: Finally, only one stone, \textbf{1}, is on the circle. This is the final state, so the answer is \textbf{1}.
\InputFile
The input consists of multiple datasets each of which is formatted as follows.
\textbf{n k m}
The last dataset is followed by a line containing three zeros. Numbers in a line are separated by a single space. A dataset satisfies the following conditions.
\textbf{2} ≤ \textbf{n} ≤ \textbf{10000}, \textbf{1} ≤ \textbf{k} ≤ \textbf{10000}, \textbf{1} ≤ \textbf{m} ≤ \textbf{n}
The number of datasets is less than \textbf{100}.
\OutputFile
For each dataset, output a line containing the stone number left in the final state. No extra characters such as spaces should appear in the output.
Input example #1
8 5 3 100 9999 98 10000 10000 10000 0 0 0
Output example #1
1 93 2019