Background

Description

【问题描述】要从n只猴子中选出一位大王。它们决定使用下面的方法： n只猴子围成一圈，从1到n顺序编号。从第q只猴子开始，从1到m报数，凡报到m的猴子退出竞选，下一次又从退出的那只猴子的下一只开始从1到m报数，直至剩下的最后一只为大王。请问最后哪只猴子被选为大王。 【输入形式】控制台输入三个整数n，m，q。 【输出形式】输出最后选为大王的猴子编号。 【样例输入】 7 4 3 【样例输出】 4

【样例说明】输入整数n ＝ 7，m ＝ 4，q ＝ 3，输出4

典型的约瑟夫问题，递推公式的思路是拿掉一只猴子之后相当于把（n-1）只猴子按一定规律重排编号之后再开始选大王。

Format

Input

Output

Samples

7 4 3

4

Limitation

1s, 1024KiB for each test case.