Description

Rumia has a unit circle, divided into $n$ equal parts, and the division points are denoted as $A_0$, $A_1$, $A_2$, $\cdots$ , $A_{n-1}$.

Now she emits a beam of light from $A_0$ toward $A_p$. After $k - 1$ reflections, it arrives at $A_t$.

Rumia wants to know the value of $t$. Since Cirno does not want to help her, Rumia turns to you for help.

Input Format

One line with three integers, $n, p, k$.

Output Format

One line with one integer $t$.

12 5 2

10

1000 342 3472844

648

Hint

Explanation of Sample 1

Physical knowledge used later

• Reflection law on a continuous curve: The incident ray and the reflected ray make equal angles with the tangent line of the curve at the point of incidence.

Constraints

This problem uses bundled testdata.

• Subtask 1 ($80\%$): $n, k \le 10^6$.
• Subtask 2 ($20\%$): $n, k \le 10^9$.

For $100\%$ of the testdata: $0 < p < n \le 10^9$, $0 < k \le 10^9$.

Postscript

• The light diagram obtained by Cirno is the legendary twelve-pointed star diagram.

Translated by ChatGPT 5