Mô tả và yêu cầu

Dãy chia hết
Cho ba số nguyên không âm 𝑁,𝐾, 𝑋 (0 ≤ 𝑋 < 𝐾 < 𝑁 ≤ 1018). Với dãy số
0,1, 2, 3, ...,𝑁 người ta sắp xếp lại dãy số đó theo quy tắc:
 Bộ các số chia 𝐾 dư 𝑋 xếp đầu tiên;
 Tiếp theo là bộ các số chia 𝐾 dư 𝑋 + 1;
 . . .
 Bộ các số chia 𝐾 dư 𝐾 – 1;
 Bộ các số chia hết cho 𝐾;
 Bộ các số chia 𝐾 dư 1;
 . . .
 Bộ các số chia 𝐾 dư 𝑋 − 1;
Trong mỗi bộ số có cùng tính chia hết, các số được sắp xếp giảm dần.
Ví dụ, 𝑁 = 10, 𝐾 = 4, 𝑋 = 2.
 Ta có: các số 10, 6, 2 chia 4 dư 2; các số 7, 3 chia 4 dư 3; các số 8, 4,0 chia hết cho
4; 9, 5, 1 chia 4 dư 1;
 Dãy số sau khi sắp xếp là: 10, 6,2, 7, 3, 8, 4,0, 9, 5, 1.
Yêu cầu: Cho 𝑄 truy vấn, mỗi truy vấn chứa ba số nguyên không âm 𝑁, 𝐾, 𝑋 và số nguyên
dương 𝐷 (𝐷 ≤ 𝑁 + 1). Tìm số thứ 𝐷 của dãy số sau khi sắp xếp.
Dữ liệu vào từ tệp văn bản DCH.INP:
 Dòng đầu tiên chứa số nguyên dương 𝑄 không vượt quá 106 là số lượng truy vấn;
 𝑄 dòng tiếp theo: Mỗi dòng mô tả một truy vấn có dạng: 𝑁, 𝐾, 𝑋, 𝐷 mỗi số cách nhau
bởi một dấu cách.
Kết quả ghi ra tệp văn bản DCH.OUT: Gồm 𝑄 dòng, mỗi dòng chứa kết quả của một truy vấn.

Ví dụ

DCH.INP               DCH.OUT                                       Giải thích
 2                     3                    Với 𝑁    =  10,  𝐾  =  4, 𝑋  =  2
 10 4 2 5              7                         Dãy       số       sau       khi       sắp       xếp       là:
 10 3 0 6                                         10,  6,2, 7, 3, 8,4, 0, 9, 5, 1.
                                                 Số thứ 5 là 3.
                                            Với 𝑁    =  10,  𝐾  =  3, 𝑋  =  0
                                                 Dãy       số       sau       khi       sắp       xếp       là:
                                                  9, 6,3, 0, 10, 7, 4, 1, 8, 5,2.
                                                 Số thứ 6 là 7.
Ràng buộc:
        Có 50% số test ứng với 50% số điểm thoả mãn: 𝑄,               𝑁  ≤  103;
        30% số test khác ứng với 30% số điểm thoả mãn: 𝑋                =  0; 𝑄  ≤  105;
        20% số test còn lại ứng với 20% số điểm không có ràng buộc gì thêm.