Rotating Duty Schedule

Version: Phuoc Hung OJ Extended

Problem Statement

There are $K$ duty teams numbered from $1$ to $K$. Team $S$ is on duty on day $1$. Each following day moves to the next team, wrapping from team $K$ to team $1$. Determine the team on duty on day $D$.

Input

One line contains three integers $K$, $S$, and $D$.

Output

Print the team number on duty on day $D$.

Subtasks

• Subtask 1 (30 points):
  • $1 \le S \le K \le 10^6$.
  • $1 \le D \le 10^6$.
• Subtask 2 (70 points):
  • $1 \le S \le K \le 10^{18}$.
  • $1 \le D \le 10^{18}$.

Examples

Example 1

Input

5 2 1

Output

2

Explanation

On day $1$ no transition has happened, so team $2$ is on duty.

Example 2

Input

5 2 5

Output

1

Explanation

The duty sequence from day $1$ to day $5$ is $2,3,4,5,1$, so day $5$ uses team $1$.

Example 3

Input

7 7 100

Output

1

Explanation

There are $99$ transitions after day $1$; $99\bmod7=1$, so one step from team $7$ reaches team $1$.