시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB159741932730.447%

문제

동호와 동호네 반 친구들은 산정호수로 소풍을 갔다. 총 N명이 소풍에 참가했고, KIN 게임을 하려고 한다. 이 게임은 다음과 같이 진행된다.

무대에 올라간 N명은 1번부터 N번까지 시계방향으로 원형으로 앉았다. 이 게임은 1번부터 시작된다. 그리고 한 명씩 시계방향으로 1, 2, ... , K까지 센다. K를 말하는 사람은 퇴장 당한다. 그 후에는 다음 자리에 앉아있는 사람이 1부터 다시 센다. 동호도 이 게임에 M번 학생으로 참가한다. 동호는 자기가 몇 번째로 퇴장 당하는지 궁금해졌다.

예를 들어, 5명의 학생이 참가하고 K=2이고, 동호는 3번 학생이라고 하면, 가장 처음에는 1 2 3 4 5와 같이 앉아있다. 1부터 게임을 시작하기 때문에, 1이 1이라고 말하고, 2가 2라고 말한다. 2가 퇴장 당한다. 3이 1이라고 말하고, 4가 2라고 말한다. 4가 퇴장 당한다. 그 다음에는 1이 퇴장 당한다. 그 후에는 5가 퇴장당하고, 마지막으로 3이 퇴장 당한다. 동호는 3번 학생이기 때문에, 5번째로 퇴장 당한다.

N, K, M가 주어졌을 때, 동호가 몇 번째로 퇴장 당하는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 세 정수 N, K, M가 주어진다.

출력

첫째 줄에 동호가 몇 번째로 퇴장당하는 지 출력한다.

제한

  • 1 ≤ N, M ≤ 5,000,000
  • 1 ≤ K ≤ N

예제 입력 1

5 2 3

예제 출력 1

5

예제 입력 2

1 10 1

예제 출력 2

1

예제 입력 3

99 100 99

예제 출력 3

94

예제 입력 4

19999 7 5

예제 출력 4

18019

예제 입력 5

99999 11111 3

예제 출력 5

69557

출처