И остался только один
Давайте сыграем в игру по удалению камней.
Изначально n камней расположены по кругу и пронумерованы 1, ..., n по часовой стрелке (Рисунок 1). Вам также даны два числа k и m. Из этого состояния удаляйте камни один за другим, следуя правилам, описанным ниже, пока не останется только один. На шаге 1 удалите камень m. На шаге 2 найдите k-й следующий камень по часовой стрелке от m и удалите его. На последующих шагах начните с места, где был удален камень на предыдущем шаге, сделайте k прыжков по часовой стрелке по оставшимся камням и удалите тот, на который попадете. Другими словами, пропустите (k−1) оставшихся камней по часовой стрелке и удалите следующий. Повторяйте это, пока не останется только один камень, и ответьте его номером.
Например, ответ для случая n = 8, k = 5, m = 3 — это 1, как показано на Рисунке 1.
Рисунок 1: Пример игры
Начальное состояние: Восемь камней расположены по кругу.
Шаг 1: Камень 3 удаляется, так как m = 3.
Шаг 2: Вы начинаете с места, которое занимал камень 3. Вы пропускаете четыре камня 4, 5, 6 и 7 (так как k = 5), и удаляете следующий, который 8.
Шаг 3: Вы пропускаете камни 1, 2, 4 и 5, и таким образом удаляете 6. Обратите внимание, что вы учитываете только камни, которые все еще находятся на круге, и игнорируете те, которые уже удалены. Камень 3 игнорируется в этом случае.
Шаги 4–7: Вы продолжаете, пока не останется только один камень. Обратите внимание, что на более поздних шагах, когда остается всего несколько камней, один и тот же камень может быть пропущен несколько раз. Например, камни 1 и 4 пропускаются дважды на шаге 7.
Конечное состояние: В конце концов, на круге остается только один камень, 1. Это конечное состояние, поэтому ответ — 1.
Входные данные
Входные данные состоят из нескольких наборов данных, каждый из которых отформатирован следующим образом.
n k m
Последний набор данных следует за строкой, содержащей три нуля. Числа в строке разделены одним пробелом. Набор данных удовлетворяет следующим условиям.
2 ≤ n ≤ 10000, 1 ≤ k ≤ 10000, 1 ≤ m ≤ n
Количество наборов данных меньше 100.
Выходные данные
Для каждого набора данных выведите строку, содержащую номер камня, оставшегося в конечном состоянии. Никакие лишние символы, такие как пробелы, не должны появляться в выводе.