Josephus Problem

In this problem, you are given n people numbered from 0 to n-1 arranged in a circle. A process is run where every k-th person is eliminated from the circle until only one person remains. Your task is to determine the safe position (0-indexed) where you should stand to be the last remaining person.

The recurrence relation for the Josephus problem is given by:

with the base case:

Make sure to read the input from stdin and print the result to stdout.

inputFormat

The input consists of a single line containing two integers n and k (1 ≤ n, k ≤ 10⁶), separated by a space. Here, n is the total number of people and k is the step size for elimination.

outputFormat

Output a single integer representing the safe position (0-indexed) where you should stand to survive.

1 1

0