798. Josephus Problem

There are n people standing in a circle, numbered from 1 to n. Starting from person 1, you count k people around the circle (including the person you start the count on), and that k-th person is eliminated. Counting then resumes from the next person, again skipping to the k-th, who is eliminated — and so on — until only one person remains.

Return the 1-indexed position of the last person remaining (the survivor). Solve it using recursion.

Input: Two integers n (number of people) and k (the count step).

Output: A single integer — the 1-indexed position of the survivor.

Examples

Input: 7, 3
Output: 4
Explanation: Eliminations: 3,6,2,7,5,1 → survivor is 4.

Input: 1, 1
Output: 1
Explanation: Only one person, who survives.

Input: 5, 2
Output: 3
Explanation: Eliminations: 2,4,1,5 → survivor is 3.

Constraints

• 1 <= n <= 1000
• 1 <= k <= 1000

Asked by