Phân phối theo vòng (Circular Distribution)

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có $M$ hộp xếp thành vòng tròn và đánh số từ $1$ đến $M$. Vật thứ nhất được đặt vào hộp $S$; mỗi vật tiếp theo vào hộp kế tiếp, sau hộp $M$ quay lại hộp $1$. Cho số lượng vật $N$. Hãy xác định hộp nhận vật thứ $N$ và số vòng đầy đủ đã hoàn thành trước khi đặt vật thứ $N$. Một vòng đầy đủ gồm $M$ vật liên tiếp, mỗi hộp nhận đúng một vật.

Input

Một dòng chứa ba số nguyên dương $M$, $S$ và $N$.

Output

In ra hai số nguyên: số hiệu hộp nhận vật thứ $N$ và số vòng đầy đủ đã hoàn thành trước khi đặt vật đó.

Subtask

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

Ví dụ

Ví dụ 1

Input

5 3 1

Output

3 0

Giải thích

Vật đầu tiên vào ngay hộp $3$. Trước khi đặt vật này chưa có vật nào, nên chưa hoàn thành vòng nào.

Ví dụ 2

Input

5 3 8

Output

5 1

Giải thích

Tám hộp nhận lần lượt là $3,4,5,1,2,3,4,5$. Trước vật thứ $8$ đã có $7$ vật; $7\div5=1$ vòng đầy đủ.

Ví dụ 3

Input

10 10 21

Output

10 2

Giải thích

Trước vật thứ $21$ đã có $20$ vật, tương ứng $20\div10=2$ vòng đầy đủ. Sau $20$ lần dịch chuyển, vị trí quay lại hộp $10$.