n people stand in a circle, numbered 1 to n in order. Starting the count at person 1 and moving around the circle, every k-th remaining person is eliminated (the count restarts from 1 immediately after each elimination, continuing in the same direction among the people still remaining). This continues until everyone has been eliminated.
Given n, k, and q, output the ORIGINAL position number (from 1 to n) of the person eliminated on the q-th elimination (so q = 1 is the very first person removed, and q = n is the last person remaining, i.e. the classic Josephus survivor).
Input format
Line 1: three space-separated integers n, k, and q.
Output format
A single integer: the original position of the person eliminated on the q-th elimination.
Constraints
- 1 <= n <= 2000
- 1 <= k <= 1000000000
- 1 <= q <= n