Circular Distribution

Version: Phuoc Hung OJ Extended

Problem Statement

There are $M$ boxes arranged in a circle and numbered from $1$ to $M$. The first item is placed in box $S$; each next item goes to the next box, wrapping after box $M$. Given $N$ items, determine the box receiving the $N$-th item and the number of complete rounds finished before placing it. A complete round consists of $M$ consecutive items, one per box.

Input

One line contains three positive integers $M$, $S$, and $N$.

Output

Print two integers: the box receiving the $N$-th item and the number of complete rounds finished before placing it.

Subtasks

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

Examples

Example 1

Input

5 3 1

Output

3 0

Explanation

The first item goes directly to box $3$. No item has been placed before it, so zero complete rounds have finished.

Example 2

Input

5 3 8

Output

5 1

Explanation

The first eight destinations are $3,4,5,1,2,3,4,5$. Before item $8$, seven items have been placed, giving $7\div5=1$ complete round.

Example 3

Input

10 10 21

Output

10 2

Explanation

Before item $21$, twenty items have been placed, giving $20\div10=2$ complete rounds. After twenty shifts, the position returns to box $10$.