Từ dãy số tự nhiên ~1, 2, 3, \ldots, N~, người ta sắp xếp lại dãy số này theo số dư trong phép chia các số hạng của dãy số cho một số tự nhiên ~K~ là ước của ~N~ như sau:

• Đoạn thứ nhất gồm tất cả các số chia hết cho ~K~.
• Đoạn thứ hai gồm tất cả các số chia ~K~ dư ~1~.
• Đoạn thứ ba gồm tất cả các số chia ~K~ dư ~2~.
• ...
• Đoạn cuối cùng gồm tất cả các số chia ~K~ dư ~K - 1~.

Các số hạng trong mỗi đoạn cũng được sắp xếp theo chiều tăng dần.

Ví dụ: Với ~N = 12~ và ~K = 4~, sau khi sắp xếp ta có dãy số:

~4, 8, 12, 1, 5, 9, 2, 6, 10, 3, 7, 11~.

Cho trước ba số nguyên dương ~N, K, M~ với ~K~ là ước của ~N~ và ~M < N~. Hãy tìm số hạng thứ ~M~ của dãy đã sắp xếp.

Input

Gồm ba số nguyên dương ~N, K, M~ (~N \le 10^{16}; K \le 10^9; K~ là ước của ~N; M < N~) trên cùng một dòng, mỗi số cách nhau một dấu cách.

Output

Ghi ra số hạng thứ ~M~ của dãy số theo yêu cầu.

Scoring

• Subtask 1 (20% số điểm): ~N \le 10^2~.
• Subtask 2 (30% số điểm): ~N \le 10^6~.
• Subtask 3 (30% số điểm): ~N \le 10^9~.
• Subtask 4 (30% số điểm): Không có ràng buộc gì thêm.

Ví dụ

Input

12 4 2

Output

8