Thanos Hates Josephus

Interview

Time limit0.1sMemory limit512 MB

Summary

Find the last squirrel left when each round keeps the first squirrel, removes the next K-1 clockwise, and the first moves to the right, for N and K up to 10^6.

Level: Medium5 of 10
Topics: Dynamic programming, Simulation
Solved: No attempts yet

Problem

$N$ squirrels sit in a circle in clockwise order, numbered from $1$ to $N$ . Thanos snapped his fingers and removed the second squirrel each time, in order. When he learned that Josephus, a mathematician from a neighboring country, had already used that method, he was annoyed. So Thanos devised a new way to remove squirrels.

Squirrel $1$ is the first squirrel at the start. When Thanos snaps, $K$ squirrels are selected clockwise starting from the first squirrel. Then the squirrels $2,$ $\cdots$ $,$ $K$ th, excluding the first, are removed in increasing order of number, and only the first squirrel survives. However, if fewer than $K$ squirrels remain, every squirrel except the first is removed. After the removal, if at least $2$ squirrels remain, the squirrel to the right of the first becomes the new first squirrel, and the process repeats. The process continues until $1$ squirrel remains.

Given $N$ and $K$ , find the number of the squirrel that remains last.

Input

The first line contains integers $N$ and $K$ , separated by a space. ( $2 \leq N, K \leq 10^{6}$ )

Output

Print the number of the last remaining squirrel.

Hint

Let us love animals.

Examples2

Example 1
Input
```
5 4
```
Expected output
```
5
```
Example 2
Input
```
1007 15
```
Expected output
```
871
```