Bài toán Josephus

Có ~n~ người đứng thành một vòng tròn và bắt đầu từ người đầu tiên, đếm theo thứ tự, cứ đến người thứ ~k~ thì người đó sẽ bị loại khỏi vòng tròn. Quá trình này tiếp tục cho đến khi chỉ còn lại một người duy nhất. Nhiệm vụ của bạn là xác định vị trí (index từ 1) của người sống sót cuối cùng.

Ví dụ minh họa:

Giả sử ~n = 5~ và ~k = 3~:

• Bắt đầu: [1, 2, 3, 4, 5], người thứ 3 bị loại (3).
• Còn lại: [1, 2, 4, 5], người thứ 6 (vòng lại là người thứ 1) bị loại (1).
• Còn lại: [2, 4, 5], người thứ 3 bị loại (5).
• Còn lại: [2, 4], người thứ 3 (vòng lại là người thứ 2) bị loại (2).
• Người cuối cùng còn lại là 4.

Vậy vị trí người sống sót cuối cùng là 4 (nếu đánh số từ 1).

Input

5 3
1 2 3 4 5

Output

4

Ràng buộc:

• 30% số test ứng với 30% số điểm có ~N \leq 1000~ và ~k \leq 1000~.
• 30% số điểm còn lại có ~N \leq 100,000~ và ~k \leq 1000~.
• 40% số test ứng với 40% số điểm có ~N \leq 10^{18}~ và ~k=2~.