187. The Josephus Problem

Challenge1000 ms256 MBSolved by 0%

n people stand in a circle, numbered 1 to n. Counting starts at person 1; every kth person is removed from the circle, and counting continues from the next person still standing.

Print the number of the last person remaining.

With n = 5 and k = 2, the removal order is 2, 4, 1, 5 — so person 3 survives.

Constraints - `1 ≤ n ≤ 100000` - `1 ≤ k ≤ 100000`

Input

A single line containing two integers n and k, separated by a space.

Output

Print one integer — the number of the surviving person, between 1 and n.

Input5 2

Output3

Noteis the worked example from the statement

Input1 1

Output1

Noteis a single person, who survives without any counting

Hint 1Approach

Hint 2Approach

Hint 3Pseudocode

Hint 4Full solution