| Little Johnny and his friends play a lot of games in which each player gets a different role. The roles are assigned using a method reminiscent of "eenie meenie miny moe" rhymes. **n** kids stand in a circle and are numbered from 1 to **n** going in a clockwise direction. They choose a number **m**, and starting with kid 1, they go around the circle in a clockwise direction, counting off from 1 to **m**. The kid who gets number **m** is eliminated from the circle, and the counting starts again at 1 with the next kid. The ith eliminated kid gets the ith role in the game. Johnny wants to know what role he will get if he is kid number **k** in the circle.
For example, consider the case where **n** = 5, **m** = 2, and **k** = 3. The kids are arranged clockwise as follows: 1, 2, 3, 4, 5. Starting with kid 1, they start counting from 1 to 2. Kid 2 gets number 2, so he is eliminated from the circle, which now looks like: 1, 3, 4, 5. They start counting again with kid 3. Kid 4 gets number 2 this time, so he is the next to get eliminated. Then, kid 1 is eliminated, followed by kid 5, and finally, kid 3. Johnny is kid 3, so he is the 5th kid to get eliminated, and he is assigned the 5th role.
Given **n**, **m**, and **k**, return the role assigned to Johnny. Roles are 1-indexed, so the 1st eliminated kid gets role 1, the 2nd eliminated kid gets role 2, and so on. |