Từ dãy số tự nhiên 1;2;3;...;N người ta sắp xêp lại dãy số này theo số dư trong các phép chia các số hạng của dãy số cho một số lự nhiên K là ước nào đó 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ố sau: 4;8;12;1;5;9;2;6;10;3;7;11

Yêu cầu: Cho trước 3 số nguyên dương N;K;M (với K là ước của N và M<N). Tìm số hạng thứ M của dãy đã sắp xếp.

Dữ liệu

• 3 số nguyên dương N;K;M (N≤10¹⁶;K≤10⁹; 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.

Kết quả

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

Giới hạn

• Có 20% test ứng với N≤102;
• Có 30% test ứng với 102<N≤106;
• Có 30% test ứng với 106<N≤109;
• Có 20% test ứng với 109<N≤1016.

Nguồn: THTB - Cấp TP 2021.