Description

The $n$ people are numbered $1 \sim n$. If they stand in a circle clockwise in order of their numbers, starting from the person numbered $1$, they count clockwise.

(The counting starts from $1$.) When the count reaches $k$, that person leaves the circle. The next person starts counting again from $1$.

Find the number of the last remaining person. This is the famous Josephus Circle problem.

In this problem, given $n$ and $k$, you need to find the number of the last remaining person.

Input Format

The input is one line containing two integers $n,k$ separated by spaces.

Output Format

Output one integer, representing the number of the last remaining person.

10 3

4

Hint

$0<n,k<10^6$.

Time limit: 1 second, 256M. The 9th Lanqiao Cup National Contest in 2018.

Translated by ChatGPT 5